백준[JS] > 2606번 바이러스

문제

https://www.acmicpc.net/problem/2606

풀이

DFS로 접근하여 문제로 풀수 있었다. 일단 컴퓨터간 모든 연결정보를 근간으로 2차원 배열로 connectionMap을 만들었다 ( connectionMap[i][j] = true 일 경우 i+1 번 컴퓨터와 j+1 번 컴퓨터는 서로 연결되어 있고 false일 경우 연결되지 않음 ) dfs를 통해 한번 탐색에 들어간 컴퓨터의 연결정보를 다시 탐색하지 않도록 visited 라는 Array를 이용하였다. ( dfs를 통해 탐색하는 동안 isVisited[ i ] = true 일 경우 해당 컴퓨터는 이미 dfs를 통해 탐색이 된 상태 ) 그렇게 dfs 를 통해 1번 컴퓨터와 연결된 모든 컴퓨터들을 탐색하면 isVisited에 true 갯수는 1번 컴퓨터 자기자신을 포함해 연결된 모든 컴퓨터의 갯수를 확인할 수 있다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [computerCount, caseCount, ...connections] = input;

computerCount = Number(computerCount);

const connectionMap = Array.from({ length: computerCount }, () => {
    return Array(computerCount).fill(false);
});

connections.forEach((connection) => {
    let [computer1, computer2] = connection.split(" ").map((n) => Number(n));
    connectionMap[computer1 - 1][computer2 - 1] = true;
    connectionMap[computer2 - 1][computer1 - 1] = true;
});

let visited = Array(computerCount).fill(false);

const dfs = (visitComputer) => {
    visited[visitComputer] = true;
    connectionMap[visitComputer].forEach((isConnected, computerIdx) => {
        if (isConnected && !visited[computerIdx]) {
            dfs(computerIdx);
        }
    });
};

dfs(0);

const answer = visited.reduce((acc, cur) => {
    if (cur === true) {
        return acc + 1;
    }
    return acc;
}, 0);

console.log(answer - 1);