'백준 1068번' 태그의 글 목록

백준 1068번

2018. 10. 2. 15:25

BOJ(백준) 1068번 트리

문제 : 입력으로 주어진 트리에서 한 노드를 지웠을 때, 남은 트리에서 리프 노드 개수 구하기.

설명:

루트부터 자식들을 BFS로 계속 찾아가는 방법으로 풀었다. 각 노드에 방문시 확인해주면서 leaf 노드의 개수를 추가한다.

확인하는 것 = 1. 만약 자식의 개수가 1개고, 그 자식이 삭제한 노드이면 . Leaf 노드 이므로 결과값에 +1

2. 만약 자식이 없으면 Leaf 노드이므로 결과값에 +1

주어진 입력에서 각 노드의 부모를 배열로 입력받는다. ex) -1 0 0 1 1 --> 0번 노드는 root이고, 1번,2번 노드의 부모는 0번 노드이고, 3,4번 노드의 부모는 1번 노드이다.

=> 이 입력을 바꾸어서, parent node 번호에 자식 node 번호를 저장한다.

adj[노드 번호] 에는 해당 노드의 자식 번호들이 저장되어있다.

(문제 바로가기 : boj.kr/1068)

import java.io.BufferedReader

import java.io.InputStreamReader

import java.util.*

fun main(args: Array<String>) {

    val br = BufferedReader(InputStreamReader(System.`in`))

    val n = br.readLine()!!.toInt()

    val adj = Array(n) { LinkedList<Int>() }

    var root = 0

    var tmp = 0

    val st = StringTokenizer(br.readLine()!!)

    while (st.hasMoreTokens()) {

        val parent = st.nextToken().toInt()

        if (parent != -1) {

            adj[parent].add(tmp++)

        } else root = tmp++

}

    val remove = br.readLine()!!.toInt()

    val q = LinkedList<Int>()

    var res = 0

    q.add(root)

    while (!q.isEmpty()) {

        val here = q.poll()

        if (here == remove) continue

        if (adj[here].size == 0 || (adj[here].size == 1 && adj[here][0] == remove)) {

            res++

            continue

}

        for (next in adj[here]) {

            if (next != remove) {

                q.add(next)

}

}

}

    println(res)

}

PREV 1 NEXT