[백준] 1260 DFS와 BFS node.js

문제 링크

1260번: DFS와 BFS

 

문제 유형

DFS/ BFS

 

문제 풀이

공통)

• 각 정점과 연결된 정점의 번호를 2차원 배열 graph에 담는다.
  (정점이 여러 개인 경우에 정점 번호가 작은 것부터 먼저 방문해야하므로 연결된 정점의 번호를 오름차순으로 정렬했다.)
  [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []]  => 1번과 연결된 정점: 2, 3, 4  / 2번과 연결된 정점: 1, 4...
• stack, queue에는 현재 방문한 정점과 연결된 정점의 번호를 추가한다.
• visited에는 각 정점의 방문 여부를 저장한다.

DFS)

   빈 스택이 될 때까지 다음을 반복한다.

1. 스택에서 노드를 꺼낸다.
2. 해당 노드를 처음 방문하는 경우
   2-1. 방문 여부를 true로 변경한다.
   2-2. 순서를 기록한다.
   2-3. 현재 정점과 연결된 정점들을 스택에 추가한다.

   더 이상 탐색할 노드가 없는 경우 반복문을 종료하고 기록한 방문 순서를 리턴한다.

 

BFS)

  빈 큐가 될 때까지 다음을 반복한다.

1. 큐에서 노드를 꺼낸다.
2. 해당 노드를 처음 방문하는 경우
   2-1. 방문 여부를 true로 변경한다.
   2-2. 순서를 기록한다.
   2-3. 현재 정점과 연결된 정점들을 큐에 추가한다.

  더 이상 탐색할 노드가 없는 경우 반복문을 종료하고 기록한 방문 순서를 리턴한다.

 

코드

// DFS
function DFS(n, v, graph) {
  const stack = [v]; // 탐색을 시작할 노드의 번호를 스택에 넣는다.
  const visited = new Array(n + 1).fill(false);
  let answer = "";

  while (stack.length !== 0) {
    // 탐색할 노드가 더 이상 없을 때까지 반복한다.
    const node = stack.pop();
    if (!visited[node]) {
      visited[node] = true;
      answer += node + " ";

      for (i = graph[node].length - 1; i >= 0; i--) {
        if (!visited[graph[node][i]]) {
          stack.push(graph[node][i]);
        }
      }
    }
  }
  return answer;
}

// BFS
function BFS(n, v, graph) {
  const queue = [v];
  const visited = new Array(n + 1).fill(false);
  let answer = "";

  while (queue.length !== 0) {
    const node = queue.shift();
    if (!visited[node]) {
      visited[node] = true;
      answer += node + " ";

      for (let i = 0; i < graph[node].length; i++) {
        if (!visited[graph[node][i]]) {
          queue.push(graph[node][i]);
        }
      }
    }
  }
  return answer;
}

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

let input = [];
rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점의 번호
  const [N, M, V] = input
    .shift()
    .split(" ")
    .map((v) => +v);

  // graph: 각 인덱스 노드에 연결된 노드를 나타낸다.
  const graph = new Array(N + 1).fill([]);
  input.forEach((e) => {
    const [a, b] = e.split(" ").map((v) => +v);
    graph[a] = [...graph[a], b];
    graph[b] = [...graph[b], a];
  });

  graph.forEach((e) => {
    e.sort((a, b) => a - b);
  });
  console.log(DFS(N, V, graph));
  console.log(BFS(N, V, graph));
  process.exit();
});

 

느낀 점

백준 사용 시 항상 입력으로 /dev/stdin을 사용해왔는데 입력 때문에 계속 런타임 에러가 났다.

readline으로 입력받는 것도 공부를 해야겠다..