[JS] 백준 바이러스 자바스크립트

문제

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

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

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

입력

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

출력

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

 

 

풀이

1. 어느 것이 연결되어있는지 연결 정보를 배열에 저장(단방향 아니고 양방향이라서 연결 양쪽으로)

2. 1번에서 시작해서 연결되어있으면 계속해서 진행하면서 cnt 증가

-> 검증 절차 :

    일단 queue의 첫번째 요소(current)를 뺴면서

    그 adjArr[current]가 비지 않았다면, 그 배열을 돌면서 다음 next값을 queue에 넣고 visited에 방문 표시해준다.

 

------

틀린 이유 :

1. visited 배열에 첫번째 1번 노드 방문했다고 안 알려줌

2. visited 배열을 이차원 배열로 만듦. 그냥 노드 들렀는지 확인하러면 그냥 1차원 배열이면 되는데 이차원 배열로 만들어서 visited[1] 안에 next를 넣어주는 식으로 했음. 이렇게 할 경우 2번노드, 3번 노드에 방문했는지 검사하는게 아니고 1번에서 2번노드를 방문했는지 여부를 검사하는 거임,  1번에서 2번으로 갈때도 2번에서 1번으로 갈떄도 그냥 다 true로 나오니까 왔다갔다 할 때마다 cnt를 증가시킴.

3. 이전 습관처럼 while(queue)로 검사. 자바스크립트에서는 이렇게 queue가 빈 배열인지 검사하는 게 안됨! queue가 비었는지 검사하려면 queue.length <0 로 했어야 함. 

4. queue.lengh로 오타냄.

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

const N = Number(input[0])
const nodeCnt = Number(input[1])

//연결 이차원 배열
const adjArr = new Array(N+1).fill(0).map(()=> new Array());

for (let i=2; i<2+nodeCnt; i++){
    let num1 = input[i].split(" ").map(Number)[0];
    let num2 = input[i].split(" ").map(Number)[1];

    //양방향 연결
    adjArr[num1].push(num2)
    adjArr[num2].push(num1)
}


function bfs(start){
    const queue = []
    queue.push(start)
    const visited = new Array(N+1).fill(false);
    visited[start] = true;
    let cnt = 0
    while(queue.length > 0){
        let current = queue.shift();
        if (adjArr[current] && adjArr[current].length != 0){
            for (let e of adjArr[current]){
                if(!visited[e]){
                    visited[e] = true;
                    queue.push(e)
                    cnt++
                }
            }
        }
    }
    return cnt
}

console.log(bfs(1))