[Python/파이썬] 백준 15900번 나무 탈출

15900번: 나무 탈출

 

코드

from collections import deque
import sys
input = sys.stdin.readline

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

# BFS
q = deque([1])
dist = [int(1e9)]*(n+1)
dist[1] = 0
total = 0
while q:
    now = q.popleft()
    for nx in edges[now]:
        if dist[nx] > dist[now]+1:
            q.append(nx)
            dist[nx] = dist[now]+1
    if len(edges[now]) == 1 and now != 1:
        total += dist[now]


print("Yes" if total % 2 == 1 else "No")

 

트리의 루트 노드를 제외한 각 노드는 단 하나의 부모 노드를 가지기 때문에 이 게임에서 리프노드의 말을 루트노드로 옮기는 경로는 루트노드에서 그 리프노드로 가는 최단경로와 같다. 그러므로 BFS를 사용하여 루트노드에서 모든 리프노드까지의 최단거리를 구하였다.

 

BFS와 똑같이 진행하는데 다른 점은 방문처리만 표시하는 것이 아니라 dist배열에 리프노드에서부터 각 노드로의 최단거리를 저장한다는 점이다. 그리고 q에서 pop한 now가 edges[now]의 길이가 1인 노드, 즉 부모노드와만 연결되어 있고 자식노드는 없는 리프노드라면 그 노드까지의 거리인 cnt를 total에 더하여서 모든 리프노드까지의 최단거리의 합 total을 구한다.

 

성원이는 먼저 시작했기 때문에 total이 홀수가 되는 경우에 이길 수 있다.