[Baekjoon] 바이러스

문제

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

풀이

BFS(너비우선탁색), Queue(큐)를 이용하여 해결

1. 주어진 input값으로 이루어진 graph를 생성
2. 컴퓨터들의 상태가 담길 distance를 생성
3. 1번 컴퓨터와 연결된 모든 컴퓨터를 0 => 1 로 변경
4. distance 배열중 1인 요소들의 개수를 return

Code

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

const [total, node, ...list] = input
const graphElements = list.map(ele => ele.split(' ').map((node) => Number(node)))

const graph = Array.from(Array(Number(total) + 1), () => [])

graphElements.forEach(([start, dest]) => {
  graph[start].push(dest);
  graph[dest].push(start)
})

const distance = Array(Number(total) + 1).fill(0)
const queue = [1];

while(queue.length > 0) {
  const start = queue.shift();
  graph[start].forEach(dest => {
    if (distance[dest] === 0) {
      queue.push(dest);
      distance[dest] = 1
    }
  })
}

const answer =  distance.filter(node => node === 1).length - 1;
console.log(answer)