[ 17073 ] [ BFS ] 나무 위의 빗물

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

17073번: 나무 위의 빗물

 

---

풀이 과정

---

1. 전반적인 과정은 BFS로 진행
   1. 루트 노드(1)부터 시작한다.
   2. 현재 노드에서 연결된 자식 노드 수만큼 물을 나누어서 배분시켜 준다.
   3. 나누어준 자식 노드로 이동하여서 다음 자식노드에게 물을 나누어준다.
   4. 2-3 과정을 반복한다.
2. 이 때, 자식노드가 존재하여 자식노드에게 물을 나누어준 경우에는 비교를 위해 값을 0으로 설정한다. 소숫점 비교는 잘 되지 않음.
3. BFS가 종료되면, 물의 양의 합계 / 물의 양이 0이 아닌 노드의 갯수 를 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N, W = map(int, input().split())
t = [[] for _ in range(N+1)]
v = [0] * (N+1)
v[1] = W

for _ in range(N-1):
    a, b = map(int, input().split())
    t[a].append(b)
    t[b].append(a)

visited = set()
visited.add(1)
queue = deque([1])

while queue:
    node = queue.popleft()
    count = 0
    for nx in t[node]:
        if nx not in visited:
            count += 1

    if count == 0:
        continue

    each_value = v[node] / count
    for nx in t[node]:
        if nx not in visited:
            v[nx] = each_value
            visited.add(nx)
            queue.append(nx)
    v[node] = 0

count = 0
for i in range(1, N+1):
    if v[i] != 0:
        count += 1

print(sum(v) / count)