백준 2606 - 바이러스

문제

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

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

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

solution

꽤 쉬워 보이는데 생각보다 반례(사실 문제만 잘 이해했으면 반례라고 하기도 좀 그럼)가 많은 문제인듯

1번 컴퓨터가 바이러스에 걸렸기 때문에, 1번과 연결되어있는 컴퓨터를 찾고, 그 컴퓨터와 연결되어있는 컴퓨터를 찾고...를 반복해주면 되는데

테스트 케이스처럼 1 2 - 이렇게 되어있는건 사실 1번과 2번이 연결되어있다고 볼 수 있지만, 2번과 1번이 연결되어 있다고 볼 수도 있음
결론은 항상 두개의 값을 모두 체크해 줘야한다는 소리

 

이후로는 그냥 dfs 구현하는 것처럼 1번이 들어있는 모든 값을 큐에 넣는다 - 하나씩 shift() 해주면서 값 두개는 바이러스 걸렸다는 표시를 해 주고, 이 두 값이 하나라도 있는 배열은 다 큐에 넣어주면서 큐가 빌때까지 반복해주면 됨(큐에 넣은 배열은 방문 표시)

Code

const fs = require("fs");
let input = fs
  .readFileSync("./test.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => +v));
const len = input[0][0];
const virus = Array(len + 1).fill(0);
const nums = input[1][0];
const visited = Array(nums).fill(false);
virus[1] = 1;
let result = 0;
const queue = [];
for (let i = 2; i < input.length; i++) {
  if (input[i][0] === 1 || input[i][1] === 1) {
    queue.push(input[i]);
    visited[i] = true;
  }
}
while (queue.length) {
  const [start, end] = queue.shift();
  virus[start] = 1;
  virus[end] = 1;
  for (let i = 2; i < input.length; i++) {
    if (!visited[i]) {
      if (
        input[i][0] === end ||
        input[i][1] === end ||
        input[i][0] === start ||
        input[i][1] === start
      ) {
        visited[i] = true;
        queue.push(input[i]);
      }
    }
  }

}
console.log(virus.filter((v) => v === 1).length - 1);

정답률 40퍼 치곤 쉬운데? 하다가 한 3번 연속 틀림...