[백준/1260/node.js]DFS와 BFS

DFS와 BFS의 정석같은 문제이다.
DFS랑 BFS 문제는 몇 번 풀어봤는데 풀 때마다 헷갈림..
익숙해질 만큼 풀자!

DFS와 BFS

쉽게 얘기하면 DFS는 아래로 계속 내려가고 BFS는 옆으로 계속 옮겨간다고 생각하면 된다.
그래서 DFS는 재귀나 stack을 사용하고
BFS는 queue를 사용해서 푼다.

위 문제는 모든 노드에 방문하는 문제라서 인접리스트를 사용해서 풀었다.

인접행렬을 사용해서 풀 경우 노드에 연결되지 않은 부분도 확인하기 때문에 시간복잡도가 더 증가한다.

예시

예제가 아래와 같은 경우,

5 5 3
5 4
5 2
1 2
3 4
3 1

인접리스트를

1 [2, 3]
2 [1, 5]
3 [1, 4]
4 [3, 5]
5 [2, 4]

이렇게 만들 수 있다. (오름차순으로 정렬함)

DFS로 탐색하는 경우
1. 시작점 3에서 연결된 정점 중 가장 작은 정점 번호인 1을 방문하고
2. 1에서 연결된 가장 작은 정점 번호인 2를 방문,
3. 2에서 연결된 가장 작은 정점 번호가 1이지만 1은 이미 방문했기 때문에 통과하고 5를 방문,
4. 5에서 연결된 가장 작은 정점번호인 2가 이미 방문했기 때문에 4를 방문하고 끝난다.(모든 정점 순회)

따라서 3 -> 1 -> 2 -> 5 -> 4 가 나온다.

BFS로 탐색하는 경우
1. 시작점 3에서 연결된 정점중 가장 작은 정점 번호인 1을 방문하고, 그 다음 정점 번호인 4를 방문, 그리고 3에서 연결된 정점이 더이상 없으므로 다음으로 넘어간다.
2. 시작점과 첫번째로 연결된 정점 1과 연결된 2와 3을 방문하는데 3은 이미 방문했으므로 넘어간다. 그리고 1에서 연결된 정점이 없으므로 다음으로 넘어간다.
3. 시작점과 두번째로 연결된 정점 4와 연결된 3과 5를 방문하는데 3은 이미 방문했으므로 넘어간다. 그리고 모든 정점을 방문했으므로 종료한다.

따라서 3 -> 1 -> 4 -> 2 -> 5 가 된다.

전체 코드

// 인풋값 입력받기
let fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M, V] = input.shift().split(" ").map(Number);

const line = input.map((v) => v.split(" ").map(Number));

const ansDfs = [];

const ansBfs = [];

const graph = Array.from({ length: N + 1 }, () => []);

let visited = Array.from({ length: N + 1 }, () => 0);

const queue = [];

// 인접리스트 만들기
for (let [from, to] of line) {
  graph[from].push(to);
  graph[to].push(from); 
 // [1,2] 일 경우 1[2] 2[1] 두 가지 경우가 나온다.
}

for (let i = 1; i < graph.length; i++) {
  graph[i].sort((a, b) => a - b); 
 // 정점 번호가 작은 것을 먼저 방문하기 때문에 오름차순으로 정렬한다.
}

function dfs(cnt) {
  if (ansDfs.length === N) return; 
  // 최대 방문 정점 수는 최대 정점 번호보다 같거나 적어야 한다.
  ansDfs.push(cnt);
  visited[cnt] = 1;
  for (let next of graph[cnt]) {
    if (!visited[next]) {
      visited[next] = 1;
      dfs(next);
    }
  }
}

dfs(V);

visited = visited.map(() => 0);
// 방문한 정점 배열 초기화

function bfs() {
  queue.push(V);
  visited[V] = 1;
  while (queue.length !== 0) {
    const now = queue.shift();
    ansBfs.push(now);
    for (let next of graph[now]) {
      if (!visited[next]) {
        queue.push(next);
        visited[next] = 1;
      }
    }
  }
}

bfs();

console.log(ansDfs.join(" "));
console.log(ansBfs.join(" "));