[백준 2606 javascript] 바이러스

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

연결되어있는 컴퓨터들의 정보가 주어지고 1번 컴퓨터가 바이러스에 걸릴때 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.

입력을 인접리스트로 바꿔준뒤에 1번에서부터 그래프 알고리즘을 사용하여 연결된 컴퓨터의 총 개수를 구하면 된다.

연결되어있는 컴퓨터의 개수만 구하면 되는것이기 때문에 DFS와 BFS중 어떤걸 사용해도 큰 지장이 없을것같았다.

일반적인 BFS 알고리즘을 구현하고 , 몇개의 노드들을 탐색했는지를 저장하는 cnt 변수를 +1 해주면 될것같다.

const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().trim().split('\n')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')
const n = Number(input.shift()) //컴퓨터의 개수
const m = Number(input.shift()) //간선의 개수
let adjList = {}
for(let i = 1;i<=n;i++)
{
    adjList[i] = []
}

// visited를 false로 초기화 시키는 함수 구현
function setVisited(){
    let visited = {}
    for(let i = 1;i<=n;i++)
    {
        visited[i] = false
    }
    return visited
}

//인접리스트 구현
for(let i = 0;i<m;i++)
{
    //각 line에 해당하는 간선
    let edge = input[i].split(' ').map(item=>+item)
    adjList[edge[0]].push(edge[1])
    adjList[edge[1]].push(edge[0])
}

// console.log(adjList)

function bfs(startVertex)
{
    //방문한 노드를 저장하는 객체 (초기값 false)
    let visited = setVisited()
    //방문할 노드를 저장하는 변수
    let needVisit = []
    needVisit.push(startVertex)
    visited[startVertex] = true
    //몇개의 노드를 방문하는지 확인하는 변수
    let cnt = 0
    //방문할 노드가 없을때까지 반복
    while(needVisit.length)
    {
        //방문하는 노드 계산
        cnt++;
        let currentVertex = needVisit.shift()
        //연결된 노드들 각각에 대한 탐색 ex) 1일때 -> 2,5 확인
        adjList[currentVertex].forEach(item=> {
            //탐색하는 노드가 방문을 하지 않았을때
            if (visited[item] === false)
            {
                //방문했다고 변경
                visited[item] = true
                //방문할 노드에 push
                needVisit.push(item)
            }
        })
    }

    //1번 컴퓨터를 제외하고 계산
    return cnt-1
}


console.log(bfs(1))

큰 어려움없이 문제가 풀렸다.
일반적인 BFS나 DFS를 구현하고 cnt++ 해주는 로직만 추가하면 문제가 쉽게 풀린다.

정리

1. 인접 리스트 만들기
2. 기본적인 BFS를 먼저 구현을 하고 그 뒤 문제가 원하는 조건(cnt 변수)을 뒤에 추가하는 식의 방식으로 문제를 풀어 나가도 좋을듯 !

끝!