[백준] 2606 바이러스 JavaScript

혅·2024년 5월 30일

백준, 프로그래머스 -JavaScript-

목록 보기

65/215

문제

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

내가 했던 풀이 방법

(n+1)×(n+1) 크기에 2차원 배열 matrix를 0으로 채워준다. (n이 아닌 n+1 크기로 하는 이유는 컴퓨터는 0번이 없기에 편하게 문제를 풀기 위해서이다.)
직접 연결되어 있는 컴퓨터일 경우, 해당 matrix에 값을 1로 바꿔준다. 예를 들어 1-2이 연결되어 있다면, matrix[1][2]와 matrix[2][1]을 1로 바꿔준다.
infected 배열은 1이 포함된 배열로 선언해준다. (infected 배열은 감염된 컴퓨터와 감염된 컴퓨터와 연결된 컴퓨터가 들어가게 된다.) 해당 컴퓨터를 검사했는지를 확인하는 visited 배열도 n+1 크기로 생성해주고 false로 채워준다.
count를 0으로 초기화해준다.
computer에 infected에 맨 앞에 있는 컴퓨터를 shift해주고 count를 1 증가시켜준다. 1부터 n까지 i를 증가시키면서 computer와 연결되어 있으면서 아직 검사하지 않은 컴퓨터를 infected에 추가해주고, 해당 컴퓨터의 visited를 true로 바꿔준다. 이를 infected가 비워질 때까지 반복한다.
모든 연산이 끝난 뒤 count-1를 출력한다. (-1을 해주는 이유는 첫 번째 반복문에서 증가된 count는 1번 컴퓨터가 감염되었음을 의미한다. 1번 컴퓨터를 통해 감염된 컴퓨터를 찾는 것이므로 1을 빼주어야 한다.)

코드

const fs = require('fs');
let [n, m, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

n = Number(n);
m = Number(m);

let matrix = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

for (let i = 0; i < m; i++) {
  input[i] = input[i].trim().split(' ').map(Number);

  matrix[input[i][0]][input[i][1]] = 1;
  matrix[input[i][1]][input[i][0]] = 1;
}

let infected = [1];
let visited = Array.from({ length: n + 1 }, () => false);
visited[1] = true;
let count = 0;
while (true) {
  if (infected.length === 0) break;
  let computer = infected.shift();
  count++;
  for (let i = 1; i <= n; i++) {
    if (matrix[computer][i] === 1 && !visited[i]) {
      infected.push(i);
      visited[i] = true;
    }
  }
}

console.log(count - 1);