[백준] 트리 (1068)(kotlin)

문제 설명

입력 및 출력

» 입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

» 출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입출력(테스트케이스)

입력	출력
5 -1 0 0 1 1 2	2
5 -1 0 0 1 1 1	1
5 -1 0 0 1 1 0	0
9 -1 0 0 2 2 4 4 6 6 4	2

문제 풀이1 (dfs)

[풀이 참고])(https://velog.io/@sukong/백준-1068-트리){:target=”_blank”}

var answer = 0

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val parents = readLine().split(" ").map { it.toInt() }
    val tree = Array(N) { mutableListOf<Int>() }
    val isVisited = BooleanArray(N)
    val target = readLine().toInt()
    var root = 0

    for (i in 0 until N) {
        if (parents[i] != -1) {
            tree[i].add(parents[i])
            tree[parents[i]].add(i)
        } else root = i
    }

    if (target == root) println(0)
    else {
        dfs(root, target, isVisited, tree)
        println(answer)
    }
}

fun dfs(node: Int, target: Int ,isVisited: BooleanArray, tree: Array<MutableList<Int>>) {
    isVisited[node] = true
    var childCount = 0

    for (i in 0 until tree[node].size) {
        var adjNode = tree[node][i]
        if (!isVisited[adjNode] && adjNode != target) {
            childCount++
            dfs(adjNode, target, isVisited, tree)
        }
    }

    if (childCount == 0) {
        answer++
    }
}

문제 풀이2 (bfs)

풀이 참고

import java.util.LinkedList

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val matrix = Array(N) { IntArray(N) }
    var rootNode = -1

    readLine().split(" ").map { it.toInt() }
        .forEachIndexed { index, node ->
            val parentNode = node

            if (parentNode == -1) {
                rootNode = index
            } else {
                matrix[parentNode][index] = 1
            }
        }

    val deletedNode = readLine().toInt()
    var leafCount = 0
    val q = LinkedList<Int>()

    if (rootNode == deletedNode) {
        println(0)
        return
    }
    q.add(rootNode)

    while (q.isNotEmpty()) {
        val current = q.poll()
        var isLeaf = true

        matrix[current].forEachIndexed { next, v ->
            if (v == 1 && deletedNode != next) {
                q.add(next)
                isLeaf = false
            }
        }

        if (isLeaf) leafCount++
    }

    println(leafCount)
}