[알고리즘/백준/1260] DFS와 BFS(비교)

문제

---

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [nums, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m, v] = nums.split(" ").map(Number);
const pairs = arr.map((pair) => pair.split(" ").map(Number));
let graph = Array.from({ length: n + 1 }, () => []);
let dfsPath = [];
let bfsPath = [];

// 인접 리스트
for (let [s, e] of pairs) {
  graph[s].push(e);
  graph[e].push(s);
}

graph = graph.map((v) => v.sort((a, b) => a - b));

function getDFSPath(v) {
  let ch = Array.from({ length: n + 1 }, () => 0);
  ch[v] = 1;
  dfsPath.push(v);

  function DFS(v) {
    for (let i = 0; i < graph[v].length; i++) {
      const nv = graph[v][i];
      if (ch[nv] === 0) {
        ch[nv] = 1;
        dfsPath.push(nv);
        DFS(nv);
      }
    }
  }

  DFS(v);
}

function getBFSPath(v) {
  let q = [];
  let ch = Array.from({ length: n + 1 }, () => 0);

  ch[v] = 1;
  bfsPath.push(v);
  q.push(v);

  while (q.length) {
    const v = q.shift();
    for (let i = 0; i < graph[v].length; i++) {
      const nv = graph[v][i];
      if (ch[nv] === 0) {
        ch[nv] = 1;
        bfsPath.push(nv);
        q.push(nv);
      }
    }
  }
}

getDFSPath(v);
getBFSPath(v);

console.log(dfsPath.join(" "));
console.log(bfsPath.join(" "));

입력 받은 그래프를 연결 되어 있는 노드 배열을 for문으로 돌면서 인접 리스트로 만든다.

DFS는 각 노드에 연결되어 있는 노드를 순회하면서 (graph[v].length) 다음 노드(nv)가 방문하지 않은 노드인 경우(if(ch[nv] === 0) 해당 노드로 바로 이동(DFS(nv))한다.

반면 BFS는 각 노드에 연결되어 있는 노드를 순회하면서 다음 노드가 방문하지 않은 노드인 경우 q에 넣고 대기한다. 동일 레벨에 있는 노드들을 모두 방문하고 난 다음에야 q에 넣어둔 노드(연결되어 있는 노드)를 방문한다.