[BOJ 골드5] 트리

문제

• https://www.acmicpc.net/problem/1068
• 탐색문제인데 이진트리 순회로 풀었다가 다시 풀었다. 인접리스트 연습좀 해야겠다

코드

var cnt = 0
lateinit var node : Array<MutableList<Int>>
lateinit var visit : BooleanArray
fun main() = with(System.`in`.bufferedReader()){
    val n = readLine().toInt()
    node = Array(n){
        MutableList(0){0}
    }
    visit = BooleanArray(n){false}
    val parent = readLine().split(" ").map{it.toInt()}
    val deleteNode = readLine().toInt()
    var root = 0
    for(i in 0 until n){
        if(parent[i]!=-1) {
            node[i].add(parent[i])
            node[parent[i]].add(i)
        }
        else root = i
    }
    dfs(root,deleteNode)
    if(deleteNode==root){
        println(0)
        return
    }
    println(cnt)

}

fun dfs(start : Int, target : Int){
    visit[start] = true
    var child = 0
    for(tNode in node[start]){
        if(!visit[tNode]&&tNode!=target){
            child++
            dfs(tNode,target)
        }
    }
    if(child==0){
        cnt++
    }
}