[Python] 백준 17073 - 나무 위의 빗물 문제 풀이

Overview

BOJ 17073번 나무 위의 빗물 Python 문제 풀이
분류: tree (트리)

---

문제 페이지

https://www.acmicpc.net/problem/17073

---

풀이 코드 1

from sys import stdin
from collections import defaultdict


def main():
    def input():
        return stdin.readline().rstrip()

    n, w = map(int, input().split())
    degrees = defaultdict(int)
    for _ in range(n - 1):
        u, v = map(int, input().split())
        degrees[u] += 1
        degrees[v] += 1

    leaf = 0
    for i in range(2, n + 1):
        if degrees[i] == 1:
            leaf += 1
    print(w / leaf)


if __name__ == "__main__":
    main()

트리에서 시간이 흐르면 빗물은 모두 리프 노드에 도달한다. 즉, 리프 노드에만 빗물이 존재하게 된다. 따라서 물의 양 / 리프 노드 개수 를 구하면 된다.

문제에서 간선 정보를 입력 받을 때, 각 노드별 간선 개수를 저장한다. 리프 노드의 간선은 부모와 연결된 간선 하나만 가진다. 따라서 degrees 값이 1인 노드의 개수는 총 리프 노드의 개수가 된다. 이렇게 리프 노드의 개수를 구한 뒤, 물의 양에 나누어 답을 구한다.

---

풀이 코드 2

from sys import stdin
from collections import defaultdict


def main():
    def input():
        return stdin.readline().rstrip()

    n, w = map(int, input().split())
    degrees = defaultdict(int)
    leaf = n - 1
    for _ in range(n - 1):
        u, v = map(int, input().split())
        degrees[u] += 1
        degrees[v] += 1

        if u != 1 and degrees[u] == 2:
            leaf -= 1
        if v != 1 and degrees[v] == 2:
            leaf -= 1

    print(w / leaf)


if __name__ == "__main__":
    main()

1번 풀이를 좀 더 짧게 줄인 코드이다. 이전 코드와 로직은 같다.