[개발일지] - 36(주말)

(1).백준 2606번 바이러스는 1번 컴퓨터에서부터 웜 바이러스가 전파될 경우

연결된 모든 컴퓨터가 바이러스에 걸린다고 가정할 때

몇개의 컴퓨터가 바이러스에 걸리는지를 묻는 문제였다.

 

간단하게 1번과 연결된 노드의 숫자를 구해야 하는 문제로

bfs로 하려고 하다가 재귀도 아니라 오버플로우도 안날 것 같아서 시간복잡도 문제로 dfs로 해결했다.

 

각 연결된 노드를 정해주고

방문한 노드가 아닐 경우에만 해당 노드를 stack에 추가했고

while을 순회할 때마다 값을 추가했는데

테스트케이스와 값이 달라 확인해보니 "감염된"컴퓨터가 아닌 "전파된"컴퓨터의 갯수였기 때문에

1번을 제외해야 해서 시작 count 변수값을 0이 아닌 -1로 시작했다.

const input = `7
6
1 2
2 3
1 5
5 2
5 6
4 7`.split('\n').map(el => el.split(' ').map(Number))
const map = []
const check = new Array(input[0][0] +1).fill(1)
let count = -1

for(let i = 0 ; i <= input[0][0] ; i++){
    map.push(new Array())
}

for(let i = 2 ; i < input.length ; i++){
    const [a, b] = input[i]
    map[a].push(b)
    map[b].push(a)
}

const stack = [1]
check[1] = 0

while(stack.length){
    const now = stack.pop()
    count++
    for(let i = 0 ; i < map[now].length ; i++){
        let node = map[now][i]
        if(check[node]){
            stack.push(node)
            check[node] = 0
        }
    }
}
console.log(count)