오늘은 그래프 문제를 풀었다. 아직 그래프에 대해 배운 적이 없어서 오늘 유독 문제를 푸는 데 어려웠다.

let input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\\n");
let start = parseInt(input[0].split(" ")[2]);
let visit = Array(1001).fill(0);
let edges = Array.from({ length: 1001 }, () => []);
let dfsResult = [];
let bfsResult = [];

for (let i = 1; i < input.length; i++) {
  let [from, to] = input[i].split(" ").map(Number);
  edges[from].push(to);
  edges[to].push(from);
  edges[from].sort((a, b) => a - b);
  edges[to].sort((a, b) => a - b); // to를 sort 해주지 않아서 틀렸던 것
}

const dfs = (cur) => {
  visit[cur] = 1;
  dfsResult.push(cur);
  for (let nxt of edges[cur]) {
    if (visit[nxt]) continue;
    dfs(nxt);
  }
};
dfs(start);

visit.fill(0);
const bfs = (start) => {
  let q = [];
  visit[start] = 1;
  q.push(start);
  while (q.length > 0) {
    let cur = q.shift();
    bfsResult.push(cur);
    for (let nxt of edges[cur]) {
      if (!visit[nxt]) {
        visit[nxt] = 1;
        q.push(nxt);
      }
    }
  }
};
bfs(start);

console.log(dfsResult.join(" "));
console.log(bfsResult.join(" "));