백준 1260 DFS와 BFS - node.js

해당 포스팅은 백준 1260번 DFS와 BFS 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였다.

---

문제

문제 설명

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

입력

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

출력

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

---

풀이

예제의 인풋으로 인접 리스트의 연결된 간선들이 주어진다. 시작점이 주어질 때 DFS와 BFS 수행 결과를 출력하라고 명시되어 있다.

따라서 인풋으로 주어지는 간선들을 연결해 그래프(인접 리스트)를 구현한 다음, DFS와 BFS 함수를 구현해 각 수행결과를 출력하면 된다.

이 때 문제에서 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하라고 나와있으므로, 간선들을 연결한 다음 각 정점에 연결된 정점들을 오름차순 정렬해야 한다.

예제를 통해 로직을 자세하게 설명하겠다.

---

로직 & 예제 설명

문제의 예제2를 통해 자세한 로직을 설명하겠다.

위의 예제의 input을 파싱하면 다음과 같다.

• 정점의 개수 N = 5
• 간선의 개수 M = 5
• 탐색을 시작할 정점의 번호 = 3
• 간선: [5,4], [5,2], [1,2], [3,4], [3,1]

먼저 인접 리스트를 만들기 위해 1) 정점들 생성, 2) 간선 연결을 한다.

1. 정점들 생성:
   문제에서 N은 1~N까지이므로 정점 1~5 만든다.
2. 간선 연결:
   간선 배열을 통해 정점들을 연결한다.
   예시로 [5,4]는 정점 5와 4를 연결하는 것이다.

그렇게 연결을 하면 그래프는 아래와 같이 만들어진다.

연결을 할 때 각 정점에 연결된 정점 list가 오름차순 정렬되어 있지 않음을 확인할 수 있다. 문제에서 뱡문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하라고 나와있으므로 각 정점 list들을 오름차순 정렬하자.

오름차순 정렬을 하게되면 맨 오른쪽 그래프가 만들어지게 된다. 이제 해당 그래프를 DFS, BFS하면 된다.

---

전체 코드

위의 로직들을 코드로 옮기면 다음과 같다.

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);

let [N, M, V] = input[0].split(" ").map(Number);
let graph =  [...Array(N+1)].map(()=>[]);

// 그래프 정점 생성
for (let i = 1; i <= M; i++) {
  let [from, to] = input[i].split(" ").map(Number);
  graph[from].push(to);
  graph[to].push(from);
}

// 그래프 각 정점에 연결된 정점 LIST 오름차순 정렬
graph.forEach((element) => {
  element.sort((a, b) => a - b);
});

// DFS
const visited_dfs = new Array(N + 1).fill(false);
const answer_dfs = [];

function dfs(V) {
    if (visited_dfs[V]) return;
    answer_dfs.push(V);
    visited_dfs[V] = true;
    graph[V].forEach((next) => {
        if (visited_dfs[next] === false) {
            dfs(next);
        }
    })
}

dfs(V);
console.log(answer_dfs.join(" "));

// BFS
const visited_bfs = new Array(N + 1).fill(false);
const answer_bfs = [];

function bfs(V) {
    const queue = [V];
    while (queue.length) {
        const curr = queue.shift();
        if (visited_bfs[curr] === true) continue;
        visited_bfs[curr] = true;
        answer_bfs.push(curr);
        graph[curr].forEach((next) => {
            if (visited_bfs[next] === false) {
                queue.push(next);
            }
        })
    }
}

bfs(V);
console.log(answer_bfs.join(" "));