[백준] 15900번 나무 탈출 파이썬 코드

코드

# 모든 노드의 depth의 합이 짝수면 No, 홀수면 Yes

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

n = int(input())
cnt = 0

tree = [[] for _ in range(n+1)]
visited = [0]*(n+1) # 방문기록
depth = [0]*(n+1) # 깊이를 기록할 리스트

for _ in range(n-1):
  x,y = map(int, input().split())
  tree[x].append(y)
  tree[y].append(x)


def bfs():
  queue = deque()
  queue.append(1)
  visited[1] = 1
  res = 0
  while queue:
    pn = queue.popleft()
    if pn != 1 and len(tree[pn]) == 1: # 리프 노드에 도달한 경우
      res += depth[pn] 
    for i in tree[pn]:
      if not visited[i]:
        visited[i] = 1
        depth[i] = depth[pn] + 1
        queue.append(i)
  return res

cnt = bfs()
print("Yes") if cnt%2 else print("No")

문제를 완벽하게 이해하지 못했었다... 리프 노드들의 깊이를 더해서 짝수면 No, 홀수면 Yes를 출력해주면 되었던 문제. 리프노드를 어떻게 찾을지가 관건이었는데, 이 문제에서는 트리에서 갈 경로가 1개이면 리프노드라고 할 수 있다. (1은 루트 노드이므로 제외)