17073 나무 위 빗물

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N,W = map(int,read().split())
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
for _ in range(1,N):
    a,b = map(int,read().split())
    graph[a].append(b)
    graph[b].append(a)

# 트리의 루트는 1번 고정
from collections import deque
q = deque()
q.append(graph[1])
visited[1] = 1

temp = 0
while q :
    connected = q.popleft()
    end_count = 0
    for now in connected :
        if visited[now] == 0 :
            q.append(graph[now])
            visited[now] = 1
        else :
            end_count += 1
    if end_count == len(connected) :
        temp +=1

print(W/temp)

3. 풀이 및 생각

문제 풀이

이 문제는 일반적인 BFS문제로 해결할 수 있다. 모든 틀은 BFS로 풀되, 마지막에 해당 노드가 말단 노드인지만 파악하기만 하면 된다.

나의 생각

근데 결과가 목표했던 시간보다 조금 초과한다. 그렇다는 것은 bfs로 푸는 문제가 아니라는 것 같다.. 일단은 넘어가자