[백준 2606] 바이러스 - dfs , javascript

문제 

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

2606번: 바이러스

 

알고리즘

0. 문제 해석 : 첫 번째 컴퓨터와 연결되어 있는 컴퓨터를 모두 찾는 문제이다

1. set 이용   : 중복되는 컴퓨터가 있을 수 있으니 set을 이용한다.

2. dfs 함수   : 반복되는 동작을 수행한다. 

 

문제 풀이

1. set과 stack에 초기 값을 넣어주고 dfs 함수를 부른다.

const set = new Set()

let stack = [1]
while(stack.length){
  const n = stack.pop()
  set.add(n)
  dfs(n)
 }

 

2. dfs 함수를 생성한다. 

이때, 경로가 한 쪽 방향에서 적힐 수 있으니 앞 뒤 모두 확인해야 한다.

function dfs(n){
    if (!visit[n]){
      visit[n] = 1
      input.slice(2).map(v=>{
        const [a,b] = v.split(' ').map(Number)
        if (a*1===n) {
          stack.push(b)
        }
        if (b*1===n){
          stack.push(a)
        }
      })
    }
    // console.log("stack")
    // console.log(stack)
  }

3. set의 크기에서 -1개 해준다.

console.log(set.size-1)

 

전체 코드 

const fs = require('fs');
const path = require('path');
const filePath = process.platform === 'linux' ? '/dev/stdin' : path.join(__dirname, '/장식.txt');
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const [all,cnt] = [input[0]*1,input[1]*1]

let visit = new Array(all+1).fill(0)
// console.log(visit)

const set = new Set()

let stack = [1]
while(stack.length){
  const n = stack.pop()
  set.add(n)
  dfs(n)
  function dfs(n){
    if (!visit[n]){
      visit[n] = 1
      input.slice(2).map(v=>{
        const [a,b] = v.split(' ').map(Number)
        if (a*1===n) {
          stack.push(b)
        }
        if (b*1===n){
          stack.push(a)
        }
      })
    }
    // console.log("stack")
    // console.log(stack)
  }
}

console.log(set.size-1)