[백준] 1260번 - DFS와 BFS (js)

문제

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

 

풀이

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

이걸 아래와 같이 정리한다.

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

1번 인덱스에 [2, 3, 4]가 있다는 것은 1과 2, 3, 4번 노드가 연결되어 있다는 뜻이다.

 

그리고 visited 배열을 둬서 갔던 곳을 다시 방문하지 않도록 true/false로 관리한다.

graph와 visited 배열 모두 0번 인덱스는 비워두고 시작해서 직관적으로 1번 인덱스가 1번 노드라는 것을 알 수 있게 한다.

 

dfs는 깊이 우선 탐색이기 때문에 for문과 재귀호출을 이용해서 구현한다.

아래로 파고들었다가 빠져나오면 for문을 이용해 형제 노드로 이동하는 원리이다.

 

bfs는 너비 우선 탐색이기 때문에 queue와 while문을 이용해 구현한다.

현재 방문한 노드의 아래 depth를 싹 다 queue에 집어넣고 queue.shift()를 통해 옆으로 이동하는 원리이다. 옆으로 이동하는 중간중간 해당 노드의 자식 노드를 queue의 뒤에 집어넣어 현재 depth가 끝나면 한 depth 아래의 맨 왼쪽부터 방문할 수 있도록 한다.

 

const fs = require('fs');
const input = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map((line) => line.trim());

function dfs(v, graph, visited, result) {
  if (visited[v]) return;

  visited[v] = true;
  result.push(v);
  graph[v].forEach((node) => {
    if (!visited[node]) {
      dfs(node, graph, visited, result);
    }
  });
}

function bfs(v, graph, visited, result) {
  const queue = [];
  queue.push(v);
  visited[v] = true;

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    graph[node].forEach((vertex) => {
      if (!visited[vertex]) {
        visited[vertex] = true;
        queue.push(vertex);
      }
    });
  }
}

function solution(input) {
  const [N, M, V] = input[0].split(' ').map(Number);
  const graph = Array.from({ length: N + 1 }, () => []);
  const visited = Array(N + 1).fill(false);
  const dfsResult = [];
  const bfsResult = [];

  for (let i = 1; i < input.length; i++) {
    const [from, to] = input[i].split(' ').map(Number);
    graph[from].push(to);
    graph[to].push(from);
  }

  for (let i = 1; i < graph.length; i++) {
    graph[i].sort((a, b) => a - b);
  }

  dfs(V, graph, visited, dfsResult);
  visited.fill(false);
  bfs(V, graph, visited, bfsResult);

  console.log(dfsResult.join(' '));
  console.log(bfsResult.join(' '));
}

solution(input);