2606번: 바이러스

백준에서 2606번: 바이러스 문제(난이도: Silver III) 확인하기

1. 문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

1-1. 입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

1-2. 출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

2. 풀이

2-1. 코드

const [N, _, ...networks] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const graph = Array.from({ length: +N + 1 }).map(() => []);
const checked = Array.from({ length: +N + 1 }).fill(false);
const infected = [];

networks.forEach(network => {
  const [start, end] = network.split(' ');

  graph[start].push(+end);
  graph[end].push(+start);
});

const dfsSearchForInfection = comp => {
  if (checked[comp]) return;

  if (comp !== 1) infected.push(comp);
  checked[comp] = true;

  graph[comp].forEach(computer => dfsSearchForInfection(computer));
};

dfsSearchForInfection(1);

console.log(infected.length);

2-2. 접근 방식

• 연결되어 있는 컴퓨터 쌍 정보를 기준으로 그래프를 만들었다. 이때 N + 1 길이의 배열을 사용한 이유는 컴퓨터 번호를 인덱스로 활용하기 위함이다.
• 1번 컴퓨터가 바이러스의 시발점이기 때문에, 1번을 '시작 정점'으로 잡고, 앞서 만든 그래프를 DFS 탐색했다. (BFS 탐색해도 아무 문제 없다. 문제에 '총 컴퓨터 수는 100개 이하'라고 명시되어 있길래 깊이 우선 탐색해도 무방할 것 같길래 더 편한 DFS를 선택했다)
• checked 배열은 이미 확인한 컴퓨터 번호를 저장하기 위해 사용했다. (처음엔 모두 false로 되어 있지만, 확인 완료한 컴퓨터 번호에 해당하는 인덱스에 위치한 값만 true로 바뀐다)
• DFS 탐색하면서 아직 확인한 적 없고 1번 컴퓨터와 연결되어 있는 컴퓨터의 번호는 infected 배열에 push 해두었다.
• DFS 탐색이 끝난 후에는 infected 배열의 길이를 출력했다.

2-3. 회고

• 해당 문제를 풀기 전에 1260번: DFS와 BFS 문제를 풀고 와서 훨씬 수월하게 느껴졌다. (나처럼 DFS/BFS가 무서운 코린이라면 풀어보는 걸 추천)
• 재귀적으로 탐색하며 수행할 로직을 머리 속으로 그리는 과정이 어렵지, 코드를 작성하는 과정을 그다지 어렵지 않았다.