백준 1068 코틀린

문제를 잘 못 읽어서 애를 먹었다.
하나의 노드에 여러개의 자식노드가 존재 가능하고(이진으로 착각ㅠ)
부모노드의 자식이 하나인데 삭제 되었을 경우 부모 노드 또한 카운트에 속하는 경우를 체크해야 한다.

remove 이후로는 탐색을 안하기 위해서 작성한 건데 급박한 시험의 경우 그냥 삭제를 해버리고 노드를 재탐색 하는게 좋을 것 같다.

 

var count = 0
val list = ArrayList<Node>()

fun main(args: Array<String>) {

    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ")
    val remove = readLine()!!.toInt()
    var root = 0
    for (i in 0 until n) {
        list.add(Node(i == remove, i))
    }

    for (i in 0 until n) {
        if (arr[i].toInt() != -1) { //루트 노드인지
            list[arr[i].toInt()].children.add(list[i])
        } else {
            root = i
        }
    }
    dfs(root)
    println(count)
}

fun dfs(position: Int) {
    val parent = list[position]
    if (!parent.remove) {
        if (parent.children.size != 0) {
            if (parent.children.size == 1 && parent.children[0].remove) { //자식이 한줄기이고 자식이 제거 되었다면 해당 노드가 leaf
                count++
            } else {
                for (node in parent.children) {
                    dfs(node.position)
                }
            }
        } else { // 자식이 없을 경우 leaf임으로
            count++
        }
    }
}

data class Node(val remove: Boolean, val position: Int) {
    val children = ArrayList<Node>()
}