[백준] 2606번 : 바이러스 (실버Ⅲ) by node.js

▷ 문제 :2606번 : 바이러스

2606번: 바이러스

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

www.acmicpc.net

▷ 해결 날짜 : 2022.04.06
▷ 소요 시간 : 20분
▷ 풀이 과정 :

1번 노드부터 시작해서 바이러스가 전염되어 연결되어있는 모든 노드의 개수를 구하는 문제였다.

BFS/DFS 뭘 써도 답이 나올 수 있는 문제인 것 같다.

풀이과정은 저번에 푼 그래프 탐색 알고리즘 기초 문제인 DFS와 BFS 문제와 동일하다.

이 문제도 그냥 기본문제인 것 같다.

▷ 구현

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

const bfs = (graph, startNode) => {
  const visited = [];
  let needVisit = [];

  needVisit.push(startNode);

  while(needVisit.length !==0){
    const node = needVisit.shift();
    if(!visited.includes(node)){
      visited.push(node);
      needVisit = [...needVisit, ...graph[node]];
    }
  }

  return visited;
};

let count = Number(input.shift());
let edge = Number(input.shift());
let grph = [...Array(count + 1)].map(e => []);

for(let i = 0 ; i < edge; i++){
  let [from, to] = input[i].split(' ').map(Number);
  grph[from].push(to);
  grph[to].push(from);
}

console.log(bfs(grph, 1).length - 1);

▷ 복기 :

단계를 좀 높여봐야겠다.