[Javascript] 백준 2606: 바이러스

문제

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

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

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

입력

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

출력

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

예제 입력 1 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 

4

 

---

문제 풀이

인풋을 다음과 같은 형태의 graph로 만듭니다.

7개의 노드가 있지만 풀이할 때 헷갈리지 않도록 +1을 해서 만들었습니다. 

1번 노드(1번 인덱스)는 2번 5번 노드와 연결되어있고, 2번 노드는 1, 3, 5 노드와 연결되어있어있고..
이렇게 끝까지 반복해서 위와 같은 형태를 만들면 됩니다! 

 

반면 visited 배열은 각 노드의 방문여부를 체크하면되므로, 2차 배열이 아닌 1차배열 형태로 만들었습니다.

(역시 헷갈리지 않도록 7개 노드 + 1의 형태로 만들었습니다)

해당 문제는 항상 1번 노드부터 시작하기 때문에 1번은 true로 미리 방문처리 해놓습니다.

이제 graph를 순회하면서 방문하지 않은 노드를 만나면 count를 +1 해주고 방문처리를 해주면 됩니다.

 

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

const N = +input.shift();
const M = +input.shift();

const graph = Array.from(Array(N + 1), () => []);
const visited = Array.from(Array(N + 1), () => false);
visited[1] = true;
let count = 0;

for (let i = 0; i < M; i++) {
  const [first, second] = input[i].split(" ").map(Number);
  graph[first].push(second);
  graph[second].push(first);
}

const dfs = (start) => {
  for (let i of graph[start]) {
    if (visited[i] === false) {
      visited[i] = true;
      count++;
      dfs(i);
    }
  }
};

dfs(1);

console.log(count);