[백준 2606번][Kotlin] 바이러스

문제 링크

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

코드

import java.util.ArrayDeque  
  
fun main() {  
    val n = readln().toInt()  
    val m = readln().toInt()  
    val connections = Array<ArrayList<Int>>(n+1) {  
        arrayListOf()  
    }  
    val visitList = Array<Boolean>(n+1) { false }  
    val deque = ArrayDeque<Int>()  
    repeat(m) {  
        val (a,b) = readln().split(' ').map{ it.toInt() }  
        connections[a].add(b)  
        connections[b].add(a)   // 방향성이 있는 그래프가 아니기 때문에 쌍방으로 저장해줘야함  
    }  
    for (item in connections[1]) {  
        deque.offerLast(item)  
    }  
    visitList[1] = true  
  
    while (deque.size > 0) {  
        val node = deque.pollLast()  
        visitList[node] = true  
        for (item in connections[node]) {  
            if (!visitList[item]) {  
                deque.offerLast(item)  
            }  
        }  
    }  
  
    val result = visitList.filter{it}.size  
    print(result-1)  // 1이 전파한 컴퓨터 개수가 답이니 1은 제외
}

설명

1과 연결되어 있는 컴퓨터를 시작으로 어디까지 연결되어있는지 깊이 우선 탐색(dfs)으로 파보면 된다.

후기

방향성이 있는 그래프가 아니라서 인덱스에 쌍방으로 데이터를 넣어줘야하는데 한 방향으로만 넣어줘서 시간을 지체시켰다. 방향이 고려되지 않는 그래프라면 어느 노드에서든 연결된 다른 노드에 접근할 수 있게 쌍방으로 데이터를 잘 저장해주자.