[백준 17073번] 나무 위의 빗물 (python)

문제

 

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

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

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

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

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

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

 

기록

(트리 3일차) 뭐든 한 번에 맞는 경우가 없다ㅜㅜ 실수한 부분들 고치느라 생각보다 많이 냈는데 그래도 어려운 문제는 아니었던 것 같다. 키포인트는 답이 W / (leaf노드 수) 라는 것!

 

코드

from sys import stdin
from collections import defaultdict

N, W = list(map(int, stdin.readline().split()))
tree = defaultdict(list)
for i in range(N-1):
    u, v = list(map(int, stdin.readline().split()))
    tree[u].append(v)
    tree[v].append(u)

leaf_count = 0
for root, nodes in tree.items():
    if root!=1 and len(nodes)==1:
        leaf_count+=1

print(round(W/leaf_count, 10))

입력된 edge 정보는 양방향으로 저장해두고 루트 노드를 제외한 edge가 하나 있는 leaf노드의 개수를 세서 W/(leaf노드 수)에 대입했더니 성공!