[백준 3182번] [Kotlin] 한동이는 공부가 하기 싫어!

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

3182번: 한동이는 공부가 하기 싫어!

 

난이도 : 실버 3
태그 : 그래프 이론, 그래프 탐색, 브루트포스 알고리즘

 

 

설명

이미 물어본 선배를 체크해가며

선배가 가르키는 다른 사람을 계속 따라가서,

이미 물어본 선배일 경우(사이클 발생), 지금까지 몇 명의 선배를 만났는지 저장하고,

 

가장 큰 수를 출력하면 됩니다.

 

 

 

소스코드

fun main() {
    val br = System.`in`.bufferedReader()

    val n = br.readLine().toInt()
    val arr = Array(n) { 0 }
    val depth = Array(n) { -1 }

    repeat(n) {
        arr[it] = br.readLine().toInt() - 1
    }

    for (i in 0 until n) {
        var idx = i
        var nowDepth = 0

        val visited = Array(n) { false }
        visited[idx] = true

        while (true) {
            idx = arr[idx]
            if (visited[idx]) break

            visited[idx] = true
            nowDepth++
        }
        depth[i] = nowDepth
    }

    println(depth.indexOfFirst { it == depth.maxOrNull()!! } + 1)
}

visited는 물어본 선배인지 체크할 배열이며,

nowDepth는 특정 선배를 시작으로 몇 단계나 거쳐갔는지를 담을 변수입니다.

 

이미 방문한 선배일 경우(사이클이 발생했을 경우) 반복문을 탈출하여, depth에 nowDepth를 저장합니다.

 

이후, 가장 depth가 깊은 선배의 번호를 출력합니다.

주의하실 점은 코틀린에서 Array.max() 사용 시 컴파일 에러가 나타나며, maxOrNull()을 사용하여야 합니다.

 

 

후기

다이나믹 프로그래밍을 섞어 조금 더 효율적으로 동작하게 코딩할 수 있을 것 같지만,

너무 귀찮았던 나머지... 그냥 제출했습니다.

 

저도 한동이와 같은 마음입니다.