python 백준 15900 나무탈출

https://www.acmicpc.net/problem/15900

로직

• 이 게임은 트리가 주어질 때 부터 선공, 후공 중 누가 이기는지 정해져 있는 게임
• root에서 leaf까지의 거리 합에 따라 승패가 정해짐
• root노드가 1인 것을 이용하여 트리를 탐색
• root에서 부터 연결된 그래프를 따라가면 leaf노드로 가게 됨
  • 방문여부를 체크 해서 루트 노드부터 체크해 나가면 밑으로만 진행 가능
• leaf노드 도달시 root에서부터 leaf까지의 거리를 누적 계산

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

def solution()->str:
    N = int(input())
    graph = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    que = deque()
    que.append(1)
    check = [False for _ in range(N+1)]
    check[1] = True

    ans,cnt = 0,0
    # bfs 방식 채택, 2중 반복문은 깊이(cnt) 계산을 위한 것
    while que:
        for _ in range(len(que)):
            node = que.popleft()
            isLeaf = True
            for next_node in graph[node]:
                if not check[next_node]:
                    check[next_node] = True
                    que.append(next_node)
                    isLeaf = False
            if isLeaf:
                ans += cnt
        cnt += 1
    if ans%2:
        return 'Yes'
    else:
        return 'No'
ans = solution()
print(ans)