[JavaScript] 백준 코딩테스트 1260. 실버 2 : DFS와 BFS

📌  문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

📌  입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

📌  출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

📌  예제 입출력

---

📌  풀이

알아야 하는 것

• DFS와 BFS가 문제의 메인이니 당연하고, 문제에서는 방문할 수 있는 정점이 여러 개 인 경우 정점 번호가 작은 것을 먼저 방문해야 하는 것과 입력으로 주어진 간선은 양방향인 점을 숙지하자. 

구할 것

• 입력 데이터 가공

const [numOfNode, numOfEdge, start] = input[0].split(" ").map(Number);

데이터의 첫 줄에는 정점의 개수, 간선의 개수, 탐색을 시작할 정점 번호가 주어진다. 이 부분을 구조 분해 할당으로 numOfNode, numOfEdge, start라는 상수에 할당한다. 이 때 데이터의 타입은 모두 String이기 때문에 split으로 분리해 배열로 만들고 바로 map으로 각 요소들을 Number화 한다.

 

• 그래프 만들기

그래프를 만들 때는 주어진 노드의 개수보다 1개 더 큰 공간을 만들어야 한다.

이후 for문으로 numOfEdge까지 돌면서 input의 값을 가져오는데, 첫 줄에는 필요한 정보들이 들어왔으니 그 다음 줄부터가 두 정점의 번호이기에 input[i+1]으로 받아야 간선의 정보를 가져올 수 있다. 이 때도 구조 분해 할당으로 from, to에 두 정점을 받고, map으로 Number화 한다. 그리고 그래프의 간선은 양방향이므로 두 번 다 넣어준다.

 

• bfs 구현

큐로 bfs를 구현하기 전, 작은 번호의 정점부터 방문하기 위해 그래프를 오름차순으로 정렬한다. 

첫 번째 예시로 하면 오름차순을 하지 않아도 되지만 두 번째 예시로 하면 확연히 다른 결과가 나온다.

오름차순으로 정렬하고 나면 [5, 1] 같은 경우에는 작은 정점부터 [1, 5]로 바뀐다. 

큐는 먼저 들어가고 먼저 나간다. 먼저 들어가는 값이 작은 값이 되기 위해 이렇게 오름차순으로 정렬한다.

그 다음 구현하는 과정은 동일하다.

 

• dfs 구현

동일하게 스택으로 dfs를 구현하기 전에 이번에는 그래프를 내림차순으로 정렬한다.

내림차순으로 정렬하면 큰 값이 먼저 나오게 정렬된다.

1번부터 진행할 때 [3, 2]가 들어가는데, 스택에서는 뒤에 것부터 pop하기 때문에 뒤에 작은 값이 와야 한다.

역시 구현하는 과정은 동일하다.

 

이후 값이 배열로 나오는데, 이 부분만 join(" ")으로 묶어주면 된다.

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// 노드 개수, 간선 개수, 탐색을 시작할 번호
const [numOfNode, numOfEdge, start] = input[0].split(" ").map(Number);

// 그래프 구현
const graph = Array.from(Array(numOfNode + 1), () => []);
for (let i = 0; i < numOfEdge; i++) {
  let [from, to] = input[i + 1].split(" ").map(Number);
  graph[from].push(to);
  graph[to].push(from);
}


// bfs 구현
function bfs(graph, start) {
  for (let i = 1; i <= numOfNode; i++) {
    graph[i].sort((a, b) => a - b); // 작은 번호의 정점부터 방문하기 위해 간선을 정렬
  }

  const visited = Array(numOfNode + 1).fill(false);
  const queue = [];
  const result = [];

  queue.push(start);
  visited[start] = true;

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

    for (let next of graph[node]) {
      if (!visited[next]) {
        queue.push(next);
        visited[next] = true;
      }
    }
  }
  return result;
}


// dfs 구현
function dfs(graph, start) {
  for (let i = 1; i <= numOfNode; i++) {
    graph[i].sort((a, b) => b - a); // 큰 번호의 정점부터 방문하기 위해 간선을 정렬
  }

  const visited = Array(numOfNode + 1).fill(false);
  const stack = [];
  const result = [];

  stack.push(start);

  while (stack.length) {
    const node = stack.pop();

    if (!visited[node]) {
      visited[node] = true;
      result.push(node);

      for (let next of graph[node]) {
        if (!visited[next]) {
          stack.push(next);
        }
      }
    }
  }
  return result;
}

console.log(dfs(graph, start).join(" "));
console.log(bfs(graph, start).join(" "));

 

dfs, bfs랑 친해져 보려고 푼 문젠데 역시 백준 입출력 값에서 시간을 많이 잡아 먹었다;

특히 fs에서 파일명 잘못 적었다고 계속 틀려서 뭐지 뭐지 한참 고민했네... ^^;