[boj] 1260. DFS와 BFS (node.js)

요약

1260

• 입력: 그래프를 이루는 정점의 개수, 간선의 개수, 시작 정점(루트 노드), 연결된 두 정점들의 목록이 주어진다.
• 출력: DFS 수행 결과, BFS 수행 결과
• 방문된 점을 순서대로 출력, 방문 가능한 점이 여러 개일 때는 작은 번호를 우선 방문.

풀이

• 문제에서 제시하는 입력값에 맞는 그래프 자료구조를 생성한 후, DFS와 BFS를 각각 수행해 탐색 결과를 순서에 유의하며 출력하는 두 과정으로 크게 나눠볼 수 있다.
• 인접 리스트를 활용해 자료구조를 구현했다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  let [N, M, V] = input().split(" ").map(Number);
  const adj = new Array(N + 1);

  while (M--) {
    const [i, j] = input().split(" ").map(Number);
    if (!adj[i]) adj[i] = [];
    if (!adj[j]) adj[j] = [];
    adj[i].push(j);
    adj[j].push(i);
  }

  for (let i = 0; i < N + 1; i++) {
    if (adj[i]) adj[i].sort((a, b) => a - b);
  }

  let result = "";
  let visited = new Array(N + 1).fill(0);
  dfs(V);

  result += "\n";
  visited.fill(0);
  let queue = [];
  bfs(V);
  console.log(result);

  function dfs(x) {
    visited[x] = true;
    result += x + " ";
    if (adj[x]) {
      adj[x].forEach((item) => {
        if (!visited[item]) dfs(item);
      });
    }
  }

  function bfs(root) {
    let visited = new Array(N + 1).fill(0);
    queue.push(root);
    visited[root] = true;
    while (queue.length > 0) {
      let x = queue.shift();
      result += x + " ";
      if (adj[x]) {
        adj[x].forEach((item) => {
          if (!visited[item]) {
            queue.push(item);
            visited[item] = true;
          }
        });
      }
    }
  }
  process.exit();
});

• 예외 상황을 꼼꼼히 확인해야 한다.
• 자바스크립트에는 queue 구조가 존재하지 않으므로, 이를 활용하기 위해서는 직접 class를 만드는 등 직접 구현해야 한다. 이때 shift 메서드를 통해 dequeue와 유사한 기능을 낼 수 있다.