[BJ / 11724] 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예시

풀이

연결요소의 개수를 구한다는 의미를 잘 생각해보아야 한다.
전체 그래프가 이어져 있지 않은 상황에서 이어져 있지 않은 것의 개수를 반환하면 된다.
visited 여부를 확인해서 count의 개수를 구해주는 것으로 구현했다.
또한 방향 없는 그래프였기 때문에, addEdge를 하는 과정에서 두 방향으로 모두 향하도록 구현했다.

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 count = 0;
    for (let i = 0; i < input[0][0]; i++) {
        graph.addVertex(i + 1);
    }

    for (let i = 1; i <= input[0][1]; i++) {
        graph.addEdge(input[i][0], input[i][1]);
    }
    for (let i = 1; i <= input[0][0]; i++) {
        if (!graph.visited[i]) {
            graph.dfs(i);
            count++;
        }
    }
    console.log(count);
});

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

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

    addEdge (v1, v2) {
        this.edge[v1].push(v2);
        this.edge[v2].push(v1);
    }

    dfs (startVertex) {
        this._dfsStackVisit(startVertex);
    }

    _dfsStackVisit (vertex) {
        let stack = [];
        stack.push(vertex);

        while (stack.length !== 0) {
            let vertex = stack.pop();

            if (this.visited[vertex]) {
                continue;
            }
            this.visited[vertex] = true;
            
            let neighbors = this.edge[vertex];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                stack.push(neighbors[i]);
            }
        }
    }
}

마무리

처음에 연결 요소의 개수에 대해 정확하게 파악하지 못했고, 방향이 없는 그래프라는 것을 자세히 보지 못해서 문제 해결에 시간을 소요했다.
문제를 꼼꼼히 읽어보고 생각한 후 문제 해결에 뛰어들어야겠다는 생각이 들었던 문제였다.