[BJ /1260] DFS와 BFS

문제

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

입력

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

출력

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

예시

풀이

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

let input = [];
rl.on("line", (line) => {
    input.push(line.split(' ').map(v => parseInt(v)));
});

rl.on("close", () => {
    let graph = new Graph();
    let startVertex = input[0][2];
    for (let i = 1; i <= input[0][0]; i++) {
        graph.addVertex(i);
    }
    for (let j = 0; j < input[0][1]; j++) {
        graph.addEdge(input[j + 1][0], input[j + 1][1]);
        graph.addEdge(input[j + 1][1], input[j + 1][0]);
    }
    console.log(graph.dfs(startVertex));
    console.log(graph.bfs(startVertex));
    console.log(graph);
});

class Graph {
    constructor() {
        this.edge = {};
        this.visited = {};
        this.printNode_dfs = "";
        this.printNode_bfs = "";
    }

    addVertex(value) {
        this.edge[value] = [];
        this.visited[value] = false;
    }

    addEdge(value1, value2) {
        this.edge[value1].push(value2);
        this.edge[value1].sort((a, b) => a - b);
    }

    dfs (startVertex) {
        this._dfsRecursiveVisit(startVertex);
        return this.printNode_dfs;
    }

    _dfsRecursiveVisit (vertex) {
        if (this.visited[vertex]) return;

        this.visited[vertex] = true;
        this.printNode_dfs += (vertex + " ");
        
        let neighbors = this.edge[vertex];
        for (let i = 0; i < neighbors.length; i++) {
            this._dfsRecursiveVisit(neighbors[i]);
        }
    }

    bfs (startVertex) {
        for (let vertex in this.edge) {
            this.visited[vertex] = false;
        }
        this._bfsLoopVisit(startVertex);
        return this.printNode_bfs;
    }

    _bfsLoopVisit (vertex) {
        let queue = [];
        queue.push(vertex);

        while (queue.length !== 0) {
            let vertex = queue.shift();
            
            if (this.visited[vertex]) continue;

            this.visited[vertex] = true;
            this.printNode_bfs += (vertex + ' ');

            let neighbors = this.edge[vertex];
            for(let i = 0; i < neighbors.length; ++i) {
                queue.push(neighbors[i]);
            }
        }
    }
}

마무리

dfs와 bfs는 graph 클래스를 만들어 해결하는 것으로 구현했다. 보통 dfs는 stack구조, bfs는 queue 구조를 활용하여 구현하는 것이 많은데, 익숙한 stack보다 dfs를 재귀를 활용하여 구현해보았다.