[Python/파이썬] 백준 17073번 나무 위의 빗물

17073번: 나무 위의 빗물

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

visited = [False]*(n+1)


def dfs(now):
    v = False
    leaves = 0
    for nx in edges[now]:
        if not visited[nx]:
            visited[nx] = True
            leaves += dfs(nx)
            visited[nx] = False
            v = True
    if not v:
        leaves = 1
    return leaves


visited[1] = True
print(w/dfs(1))

 

처음엔 어렵게 보였지만 생각해보니 자식노드가 없는 노드인 리프노드의 개수만 구하면 되는 문제였다. 어차피 물의 양은 변하지 않는다. 그러므로 리프노드의 수만 구해서 물의 양/리프노드 수를 구하면 정답이었다.

 

그렇기 때문에 DFS로 리프노드를 찾아서 그 수를 셌다. 루트 노드에서 탐색을 시작했을 때 연결된 노드 중 이미 방문하지 않은 노드가 없는 노드가 바로 리프노드이다.

 

다른 풀이도 찾아보니 그래프를 탐색하는 방식으로 하지 않고 edges 배열을 확인하여 부모노드가 1이 아니면서 연결된 노드가 1개뿐인 노드의 수를 세는 방법도 있었다. 이 방식은 해당 문제의 그래프가 루트노드를 제외하고는 부모노드가 1개뿐인 트리 형태이기 때문에 가능한 것 같다.