[BOJ]15900. 나무탈출

6338 단어 bojtreeboj

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')

부모 노드부터 차례로 주어진다고 생각했지만 끊어져서 주어지는 경우가 있어서 주의해야한다.

좋은 웹페이지 즐겨찾기