BOJ 15900 문제 바로가기
문제의 저작권은 백준 온라인저지에 있습니다.
from collections import deque
N =int(input())
# 연결이 나중에 되는 경우가 있다면?
tree=[[] for i in range(N+1)]
visited=[False]*(N+1)
q=deque()
for i in range(N-1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
q.append([1,0])
visited[1]=True
tmp_sum=0
while len(q)>0:
front=q.popleft()
is_leaf=True
for t in tree[front[0]]:
if not visited[t]:
is_leaf=False
visited[t]=True
q.append([t, front[1]+1])
if is_leaf:
tmp_sum+=front[1]
if tmp_sum%2==0:
print('No')
else:
print('Yes')
부모 노드부터 차례로 주어진다고 생각했지만 끊어져서 주어지는 경우가 있어서 주의해야한다.