백준 2688번 숫자고르기 Kotlin

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

문제

---

생각하기

---

• 방향 그래프 사이클 찾기

• DFS

동작

결과

코드

---

import java.io.File

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private lateinit var isVisited: BooleanArray
private lateinit var retList: MutableList<Int>
private lateinit var arr: IntArray

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    for (i in 1..N) {
        DFS(i, i)
    }

    retList.sort()
    sb.append(retList.size).append('\n')
    retList.forEach {
        sb.append(it).append('\n')
    }
    return sb.toString()
} // End of solve()

private fun DFS(idx: Int, target: Int) {
    if (isVisited[arr[idx]]) return

    isVisited[arr[idx]] = true
    DFS(arr[idx], target)
    isVisited[arr[idx]] = false

    if (arr[idx] == target) retList.add(target)
} // End of DFS()

private fun input() {
    N = br.readLine().toInt()

    isVisited = BooleanArray(N + 1)
    retList = mutableListOf()
    arr = IntArray(N + 1)

    for (i in 1..N) {
        arr[i] = br.readLine().toInt()
    }
} // End of input()