[NodeJs] DFS와 BFS (백준 1260번 노드JS JavaScript 자바스크립트)

문제

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

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

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

 

---

 

 

// 백준 1260 DFS와 BFS
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
//백준용 입력

// const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
//로컬용 입력
const [N, M, V] = input.shift().split(' ').map(Number);
const edges = input.map(v => v.split(' ').map(Number));

const graph = Array.from(Array(N+1), ()=> new Array().fill(0));
edges.forEach(arr=>{
    let [a, b] = arr;
    graph[a].push(b)
    graph[b].push(a)
})
graph.forEach(i=>{
    i.sort((a,b)=>b-a);
})

// DFS
const stack = [];
let visited = Array.from(Array(N+1).fill(false));
stack.push(V);

const dfsResult = [];
while (stack.length > 0) {
    x = stack.pop();
    if (visited[x]===false){
        visited[x] = true;
        dfsResult.push(x);
    }
    for (let i=0; i<graph[x].length; i++) {
        if (graph[graph[x][i]].length > 0 && visited[graph[x][i]]===false){
            stack.push(graph[x][i]);
        }
    }
}

//BFS
graph.forEach(i=>{
    i.sort((a,b)=> a-b);
})

const bfsResult = [];
const q = [];
q.push(V);
let visited2 = Array.from(Array(N+1).fill(false));
while (q.length>0){
    x = q.shift();
    if (visited2[x]===false) {
        bfsResult.push(x);
        visited2[x] = true;
    }
    for (let i=0;i<graph[x].length;i++){
        if (graph[graph[x][i]].length>0 && visited2[graph[x][i]]===false) {
            q.push(graph[x][i]);
        }
    }
}
console.log(dfsResult.join(' '));
console.log(bfsResult.join(' '));

 

DFS는 스택으로, BFS는 큐(shift)로 해결했습니다.

문제 조건 중 [ 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고..] 라는 부분을 유의해서 풀어야 합니다.

 

 

 

DFS는 스택에서 pop을 통해 가장 마지막 요소를 뽑아오고,

BFS는 큐에서 unshift를 통해 가장 첫번째 요소를 뽑아오므로

두 경우 각각 내림차순, 오름차순 정렬을 해줘야 합니다.