백준 / 그래프 / 2606번 / 바이러스 / JS

< 문제 바로가기 >

2606번: 바이러스

 

/* 바이러스 */
const fs = require('fs');
// const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const COMPUTER_COUNT = +input.shift();
const PAIR_COUNT = +input.shift();
const PAIR_LIST = input.map((pair) => {
  return pair.split(' ').map(Number);
});

function solution(COMPUTER_COUNT, PAIR_LIST) {
  let graph = {};
  const makeGraph = (PAIR_LIST) => {
    for(let i=1; i<=COMPUTER_COUNT; i+=1) {
      graph[i] = [];
    }

    PAIR_LIST.forEach(([start, end]) => {
      graph[start].push(end);
      graph[end].push(start);  
    });
  }

  const BFS = (start) => {
    let result = 0;
    let queue = [];
    let visited = Array.from({ length: COMPUTER_COUNT + 1 }, () => false);

    queue.push(start);
    visited[start] = true;

    while(queue.length) {
      let node = queue.shift();

      for(const nextNode of graph[node]) {
        if(!visited[nextNode]) {
          queue.push(nextNode);
          visited[nextNode] = true;
          result += 1;
        }
      }
    }

    console.log(result);    
  };

  makeGraph(PAIR_LIST);
  BFS(1);
}

solution(COMPUTER_COUNT, PAIR_LIST);

---

정말 전형적인 그래프 문제였다.

BFS, DFS 어느 방식으로 풀어도 상관없다.

하지만 생각해야 할것은 그래프의 노드 간 간선이 양방향이라는점만 잘 생각하고 하면 될 것 같다.

 

그리고 문제에선 단방향으로의 노드의 쌍 값만 주어지지만, 역시 위에서 말한대로 양방향을 고려해서 데이터를 인접리스트 형식으로 바꿔주고 풀이했다.