[JS] 바이러스

문제

https://www.acmicpc.net/problem/2606

 

풀이

해당 문제는 DFS와 BFS 풀이 모두 가능한 문제이다.

 

간단한 문제이기 때문에 DFS와 BFS를 다시 연습하기 위해 풀이했다.

 

 

BFS 코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n');

const n = +input.shift();
const linked = +input.shift();
const arr = input.map(e => e.split(' ').map(Number));
const map = {};
const que = [1];
const check = Array.from({ length: n }, () => false);

arr.forEach(([st, ed], i) => {
  map[st] ? map[st].push(ed) : map[st] = [ed];
  map[ed] ? map[ed].push(st) : map[ed] = [st];
});

while (que.length && linked > 0) {
  const target = que.shift();
  if (!check[target - 1] && map[target]) {
    const list = map[target];
    check[target - 1] = true;
    for (let i = 0; i < list.length; i++){
      que.push(list[i]);
    }
  }
}

const answer = check.filter(e => e === true).length
console.log(answer !== 0 ? answer - 1 : answer);

 

DFS 코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n');

const n = +input.shift();
const linked = +input.shift();
const arr = input.map(e => e.split(' ').map(Number));
const map = {};
let answer = 0;
const check = Array.from({ length: n }, () => false);

for (let i = 0; i < arr.length; i++){
  const [st, ed] = arr[i];
  map[st] ? map[st].push(ed) : map[st] = [ed];
  map[ed] ? map[ed].push(st) : map[ed] = [st];
}

const dfs = (target) => {
  if (check[target - 1] || !map[target]) {
    return;
  }
  const list = map[target];
  check[target - 1] = true;
  for (let i = 0; i < list.length; i++){
    dfs(list[i]);
  }
}

dfs(1)
answer = check.filter(e => e === true).length
console.log(answer > 0 ? answer - 1 : 0);