BFS 문제

문제

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

예를 들어 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

---

정답 코드

const readFileSyncAddress = "./input.txt";
const fs = require("fs");
const [computerNum, computerPairNum, ...input] = fs
  .readFileSync(readFileSyncAddress)
  .toString()
  .trim()
  .split("\n");

// 이차원 배열 선언과 동시에 초기화
let arr = Array.from({ length: computerNum }, () => new Array());

let visit = new Array(computerNum).fill(false); // 방문여부
let queue = [];	
let answer = 0;

//BFS
for (let i = 0; i < input.length; i++) {
  // 입력 값 저장
  const temp = input[i].split(" ");
  arr[temp[0] - 1].push(temp[1]);
  // 1과 연결된 컴퓨터 번호를 queue에 저장
  if (temp[0] == 1) {
    queue.push(temp[1]);
    answer++;
  }
  visit[0] = true;	// 1번 방문처리(인덱스이므로 -1 해줌)
}

while (queue.length !== 0) {	// queue가 빌 때까지
  let cur = queue.shift() - 1;	// queue에서 값을 꺼낸 후 -1 해줌(인덱스 기준이므로)

  if (!visit[cur]) {	// 만약 방문하지 않은 컴퓨터이면
    while (arr[cur].length !== 0) {	// 연결된 컴퓨터가 없을 때까지
      let a = arr[cur].pop();	// a에 연결된 컴퓨터 저장
      if (!visit[a - 1]) {	// a를 방문하지 않았다면
        queue.push(a);	// queue에 a를 넣어주고
        answer++;	// answer+1
      }
    }
  }
  visit[cur] = true;	// 방문 처리 해줌
}

console.log(answer);

---

문제 풀이

1. 이차원 배열을 만들어주고, 연결된 컴퓨터들을 저장해준다.

   위의 입력을 예시로 들자면

   arr = [[2 ,5], [3], [], [7], [2,6],[], []] 이 된다.

2. 첫번째 for 문을 돌고 나면 queue에는 2와 5가 저장되고, visit의 0번째에는 true가 저장된다.

3. 이후, 큐가 빌 때까지 while문을 돌면서 cur에는 큐의 첫 번째 값을 꺼내서 -1을 해준 뒤 저장한다.

   인덱스를 저장하는 것이다.

   3-1. 만약 cur을 방문하지 않았다면 arr[cur]의 값을 꺼내서 a에 저장한다.

     이때 a는 인덱스가 아닌 값이므로 -1을 해준다.

   3-2. 다시 a-1번째를 방문했는지 확인하고, 방문하지 않았다면 queue에 a값을 넣어주고 answer+1을 해준다.

     arr[cur]이 빌 때까지 3-1과 3-2의 과정을 arr[cur]이 빌 때까지 반복해주고

4. arr[cur]이 비었다면 방문처리를 해주면 된다.