[BaekJoon] 2606번 바이러스

▶ 문제 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

▶ 코드:

let input = require('fs').readFileSync(`BaekJoon/testcase.txt`).toString().split('\n');

function BFS (graph, start, num){
    const visited = Array(num).fill(false);
    const q = [];
    let count = 0;
    const firstN = graph[0];
    visited[0] = true;
    q.push(...firstN);

    while(q.length !== 0){
        const num = q.shift();    
                    
        if(visited[num]){
            continue;
        }
        visited[num] = true;
        const neighbors = graph[num];
        q.push(...neighbors);
        count += 1;
    }

    return count;
}

let [comsNum, edgeNum, ...edges] = input;
comsNum = Number(comsNum);
edgeNum = Number(edgeNum);

const graph = Array.from(Array(comsNum).fill([]));

for (let i = 0; i < edgeNum; i++){
    let [x, y] = edges[i].split(' ').map(num => Number(num));
    graph[x-1] = [...graph[x-1], y-1];
    graph[y-1] = [...graph[y-1], x-1];
}

const answer = BFS(graph, 0, comsNum);

console.log(answer);

 

▶ 문제 풀이 :

1. 컴퓨터 수의 정보와 간선의 정보를 이용해 인접행렬로 그래프를 구현한뒤 BFS함수의 인자로 graph를 넘겨주는 방식을 선택하였다.

2. BFS 함수는 배열을 Queue(큐) 자료구조와 같이 사용하며 각각의 노드가 연결되어있는 그래프 정보와 방문했는지의 visited에 대한 정보를 이용해 그래프를 탐색하고, 초기 시작인 0번 노드에서 다른 노드까지 총 몇개의 노드가 연결되어 있는지 count에 저장한다.(이때 시작점인 0번 노드의 수는 제외) 

3. BFS 함수의 결과를 출력해주면 끄읕~