[ 백준 알고리즘 ] Node.js 2606. 바이러스

1. 문제

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

 

2. 풀이방법

1) DFS 또는 BFS 로 풀어야 하는 이유

• 문제에 "전파", "확산" 이라는 표현
  • 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 바이러스에 걸린다
• 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수

 

const fs = require('fs').readFileSync(0, 'utf-8').toString().trim();
const inputs = fs.split('\n');
const N = Number(inputs[0]); // 컴퓨터의 수
const M = Number(inputs[1]); // 간선의 수

// 컴퓨터들이 연결된 그래프 생성
const graph = Array.from({length: N + 1}, () => []);
for(let i = 0; i < M; i++){
    const [a, b] = inputs[i + 2].split(' ').map(Number);
    graph[a].push(b);
    graph[b].push(a);
}

// BFS 함수
function bfs(start) {
    const queue = [];
    const visited = new Array(N + 1).fill(false); // 컴퓨터 방문 여부 확인.
    visited[start] = true;
    queue.push(start);
    
    while(queue.length > 0) {
        const cur = queue.shift()
        for(const next of graph[cur]) {
            if(!visited[next]) {
                visited[next] = true;
                queue.push(next);
            }
        }
    }
    
    // 1번 컴퓨터는 제외해야 함.
    return visited.filter(v => v === true).length - 1;
}

// 문제에서 1번 컴퓨터로부터 바이러스가 전파되기 때문.
console.log(bfs(1))