백준 17073 나무 위의 빗물 Kotlin (트리)

문제 출처 : https://www.acmicpc.net/problem/17073

17073번: 나무 위의 빗물

문제

 

트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 1번 정점을 루트로 하는 어떤 트리를 나타낸 모습이다.

사실 이 트리는 영훈이가 뒷마당에서 기르고 있는 나무이다. 어제는 비가 왔기 때문에, 트리의 1번 정점에는 W만큼의 물이 고여 있다. 1번 정점을 제외한 모든 정점에는 아직 물이 고여 있지 않은 상태이다.

이제 매초마다 모든 정점은 아래의 작업을 순서대로 반복한다.

• 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다.
• 만약 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다.

이때, 위 작업은 순서대로 진행되므로 부모 정점에게 받은 물을 즉시 자식 정점에게 줄 수는 없다.

영훈이는 나무를 바라보면서 더 이상 물이 움직이지 않는 상태가 되었을 때 각 정점에 어느 정도의 물이 있게 될지 궁금해졌다. 더 이상 물이 움직이지 않을 때, i번 정점에 쌓인 물의 양의 기댓값을 Pi라 하자. 이때, Pi가 0보다 큰 정점들에 대해서 Pi들의 평균은 어느 정도가 될까?

입력

첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109)

다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다. (1 ≤ U, V ≤ N​​​​, U ≠ V)

이는 양 끝 정점이 각각 U와 V인 간선이 트리에 존재한다는 의미이다.

입력으로 주어지는 트리는 항상 올바른 연결 트리임이 보장되며, 주어지는 트리의 루트는 항상 1번 정점이다.

출력

문제의 정답을 출력한다. 정답과의 차이가 10-3 이하인 값은 모두 정답으로 인정된다.

알고리즘 분류

• 수학
• 그래프 이론
• 그래프 탐색
• 트리

풀이

간단한 트리 문제이다.

위의 예제를 보면 루트 노드에 20만큼의 물이 있고, 이는 각각 2, 4, 5 노드에 20씩 들어갈 수 있다.

3노드는 중간 지점이므로 물이 잠시 머무를 수는 있지만 최종적으로 물이 존재하진 않는다.

따라서 이 문제는 리프 노드의 개수를 구하고, 리프 노드마다 w만큼 물이 들어갈 수 있기 때문에

w / (leafNode 수) 를 출력하면 된다.

lefatNode의 수는 어떻게 구할까?

1. 루트에서부터 dfs를 돌려 더 이상 간선이 없는 노드의 수를 센다.

2. 입력으로 주어진 양방향 간선을 이용해 Degree(차수)를 구한다.

그렇다. 2번 방법으로 빠르고 쉽게 구할 수 있다.

예제에서 노드들의 Degree는 어떻게 될까?

1 : 2

2 : 1

3 : 3

4 : 1

5 : 1

Degree가 1인 2,4,5 노드가 LeafNode임을 알 수 있다.

여기서 주의할 점은 루트노드는 OutDegree(해당 노드에서 다른 노드로 향하는 간선의 차수)가 있고, InDegree(해당 노드로 들어오는 간선의 차수)는 항상 없기 때문에 총 Degree가 1이 될 수 있다는 점이다.

따라서 루트 노드는 제외하고 나머지 노드들 중에서 LeafNode 수를 세면 된다.

코드1(dfs)

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }

lateinit var edge: Array<ArrayList<Int>>
var leafCnt = 0

fun dfs(cur: Int, visited: BooleanArray) {
    var degreeCnt = 0
    visited[cur] = true
    for (next in edge[cur]) {
        if (visited[next]) continue
        dfs(next, visited)
        degreeCnt++
    }
    if(degreeCnt == 0) leafCnt++
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, w) = getIntList()
    edge = Array(n + 1) { ArrayList() }
    repeat(n - 1) {
        val (from, to) = getIntList()
        edge[from].add(to)
        edge[to].add(from)
    }
    //solve
    dfs(1, BooleanArray(n + 1))
    //output
    write("${w/(leafCnt.toDouble())}")
    close()
}

코드2 (Degree)

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, w) = getIntList()
    val degreeCnt = IntArray(n+1)
    repeat(n - 1) {
        val (from, to) = getIntList()
        degreeCnt[from]++
        degreeCnt[to]++
    }
    degreeCnt[1] = 0
    //output
    write("${w/((degreeCnt.count { it==1 }).toDouble())}")
    close()
}