[백준] 10451번: 순열 사이클 - Kotlin[코틀린]

문제

 

10451번: 순열 사이클

 

---

풀이

 

 DFS를 활용해 순열 사이클을 구할 수 있다.

 

 입력받은 배열에는 다음으로 이동할 위치를 가르키고 있기 때문에 현재 위치는 방문 표시를 해주고 가르키는 위치로 DFS 탐색을 해주면 된다. 만약 현재 위치에서 가르키는 위치가 이미 방문했던 위치인 경우, 순열 사이클이 만들어진 것이다. 

 

 반복문을 통해 각 위치에서 시작하는 사이클을 구하면 되는데, 이미 방문했던 위치는 사이클에 포함되어 있는 것이므로 DFS를 실행하지 않는다.

 

---

코드

 

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

    val sb = StringBuilder()

    repeat(br.readLine().toInt()) {
        val num = br.readLine().toInt()
        val arr = br.readLine().split(' ').map { it.toInt() - 1 }
        val visited = BooleanArray(num)

        fun dfs(depth: Int) {
            visited[depth] = true
            val next = arr[depth]
            if(!visited[next]) {
                dfs(next)
            }
        }
        var cnt = 0
        for(i in 0 until num) {
            if(!visited[i]) {
                dfs(i)
                cnt++
            }
        }
        sb.append("$cnt\n")
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}