[javascript] 백준 11724번 연결 요소의 개수

문제보기

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split("\n")
    .map((item) => item.split(" ").map((value) => +value));

const [N, M] = input.shift();
const graph = [...Array(N + 1)].map(() => []);
const visited = [...Array(N + 1)].map(() => []).fill(false);
input.forEach(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
});
let result = 0;

const DFS = (start) => {
    let stack = [...start];
    while (stack.length) {
        let node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;
        stack.push(...graph[node]);
    }
};
for (let i = 1; i < graph.length; i++) {
    if (!visited[i]) {
        result++;
        DFS(graph[i]);
    }
}
console.log(result);

풀이

해당 정점을 방문한적이 있는지 여부를 체크 후 DFS를 실행한다.
이때 방문한적이 없다면 결과에 +1을 해준다.
DFS 실행중 방문한적이 있는 노드면 while문 안에서 continue한고 방문한적이 없다면 방문했다고 체크해준다.