[백준] 2606번 바이러스(DFS - 깊이우선탐색)[Kotlin - 코틀린]

백준 2606번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

2606번: 바이러스

문제

문제 접근

깊이 우선 탐색(DFS)을 활용하여 1번 컴퓨터와 연결되어있는 컴퓨터들의 개수(바이러스 감염)를 출력하면 되는 문제입니다.

방문 판단을 하기위하여 visited라는 BooleanArray를 만들어 주었습니다.

visited[3] = false 는 3번 컴퓨터에 방문하지 않았다는 뜻, visited[5] = true 는 5번 컴퓨터에 방문하였다는 뜻 입니다.

 

컴퓨터간의 연결 정보를 담을 netWork라는 Array<MutableList<Int>>를 만들어주었습니다. 

netWork[1]에는 1번 컴퓨터와 연결되어있는 컴퓨터들의 번호가, netWork[5]에는 5번 컴퓨터와 연결되어있는 컴퓨터들의 번호가 담겨있습니다.

예제 입력 1 기준 netWork의 그래프틑 아래와 같이 구성되어 있습니다.

[] // 0번 컴퓨터는 존재 x
[2, 5] // 1번 컴퓨터는 2번, 5번 컴퓨터와 연결되어있음.
[1, 3, 5] // 2번 컴퓨터는 1번, 3번, 5번 컴퓨터와 연결되어있음.
[2] // 3번 컴퓨터는 2번 컴퓨터와 연결되어있음.
[7] // 4번 컴퓨터는 7번 컴퓨터와 연결되어있음.
[1, 2, 6] // 5번 컴퓨터는 1번, 2번, 6번 컴퓨터와 연결되어있음.
[5] // 6번 컴퓨터는 5번 컴퓨터와 연결되어있음.
[4] // 7번 컴퓨터는 4번 컴퓨터와 연결되어있음.

각 컴퓨터들은 방향이 없는 간선이기 때문에 양쪽에 연결 정보를 모두 입력해줍니다.

 

dfs함수는 깊이우선 탐색을 진행하는 함수입니다.

바이러스는 1번 컴퓨터로부터 시작되기 때문에 1번 컴퓨터에서 부터 연결되어있는 컴퓨터들을 확인하고 1번 컴퓨터에서 연결되어있는 컴퓨터(2,5)들을 확인하고 해당(2,5)번 컴퓨터들과 연결되어있는 컴퓨터들(2 - 1,3,5 | 5 - 1,2,6)을 확인하고.. 이런식으로 1번에서 연결되기 시작한 모든 컴퓨터들을 확인해준다. 중복 탐색을 방지하기 위하여 visited변수를 사용하여 이미 확인한 컴퓨터라면 건너뛰고 그렇지 않으면 ans에 +해주는 식으로 진행하였습니다.

정답 코드

lateinit var visited: BooleanArray
lateinit var netWork: Array<MutableList<Int>>
var ans = 0
fun main() {

    // 컴푸터의 수
    val cntOfCom = readln().toInt()
    // 컴퓨터 쌍의 수
    val cntOfLine = readln().toInt()

    netWork = Array(cntOfCom + 1, { mutableListOf() })
    visited = BooleanArray(cntOfCom + 1, { false })

    repeat(cntOfLine) {
        val (a, b) = readln().split(" ").map { it.toInt() }
        netWork[a].add(b)
        netWork[b].add(a)
    }

    dfs(1)
    println(ans)

}

fun dfs(start: Int) {
    visited[start] = true
    for (connectedCom in netWork[start]) {
        if (visited[connectedCom] == false) {
            visited[connectedCom] == true
            ans += 1
            dfs(connectedCom)
        }
    }
}