[백준2606_자바스크립트(javascript)] - 바이러스

🔴 문제

바이러스

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');

const networks = Array.from({ length: Number(inputs[0]) }, () => []);
const computers = Array.from({ length: Number(inputs[0]) }).fill(false);
const q = [1]; // 1번 컴퓨터 시작

for (const input of inputs.splice(2, inputs.length - 2)) {
  const [a, b] = input.split(' ').map(Number);
  networks[a - 1].push(b);
  networks[b - 1].push(a);
}

while (q.length) {
  const target = q.shift() - 1;

  computers[target] = true;
  for (const network of networks[target]) {
    if (!computers[network - 1]) q.push(network);
  }
}

console.log(computers.filter((it) => it).length - 1);

🟢 풀이

⏰ 소요한 시간 : -

아 문제는 네트워크 문제유형으로 bfs로 풀이할 수 있다.
보통 나는 인접 리스트 형태로 네트워크 정보를 저장해주었고, 바이러스에 걸렸는지, 안걸렸는지 컴퓨터의 상태를 확인하는 배열 computers를 추가로 만들어주었다.

for (const input of inputs.splice(2, inputs.length - 2)) {
  const [a, b] = input.split(' ').map(Number);
  networks[a - 1].push(b);
  networks[b - 1].push(a);
}

입력의 3번째 줄부터 끝까지 반복하면서 연결되어있는 요소를 networks 배열에 푸시해주었다. 여기서 중요한점은 이 문제에서 연결된 네트워크는 양방향 통신을 할 수 있기 때문에 두 개의 컴퓨터 모두에서 체크를 해주어야 한다. 그리고 1번 컴퓨터부터 바이러스가 전파되기 때문에 큐에 1번을 넣어준 후 큐가 빌때까지 bfs 로직을 수행해주면 된다.
이 때 1번 컴퓨터는 0번 인덱스에 있으므로 큐에서 shift()를 수행하면서 1을 빼준다.
바이러스에 감염처리(방문처리)를 해주고 해당 컴퓨터와 연결된 컴퓨터중 바이러스에 감염되지 않은 컴퓨터만 큐에 넣어준다.
1번 컴퓨터를 제외해야 하므로 -1해줘서 정답 출력

🔵 Ref