[백준/BOJ] - 15900번 python 풀이 - dfs

---

성원이와 형석이가 번갈아가며 리프 노드에 있는 말을 옮기는 동작을 수행한다.

승리 조건은 자기 손으로 직접 현존하는 말을 모두 없애버리는 것이다.

성원이가 먼저 시작한다고 하였기에 리프노드의 depth의 합이 홀수라면 성원이가 이기게 될 것이다.

ex) 리프노드의 depth의 합이 1이라고 가정하면 성원이가 말을 한번 옮기는 순간 현존하는 말이 모두 없어진다.

 

결국, 노드 마다 depth의 값을 저장하고 그 중 리프노드를 걸러내어 그 depth의 합이 짝수인지 홀수인지 여부를 따지면 된다.

 

시간초과가 나서 pypy3로 해결.

정확히 무슨 이유인지는 모르겠지만 재귀 깊이 제한을 10^6으로 하면 메모리 초과가 난다.

---

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n = int(input()) #노드 개수
cnt = 0
arr = [[] for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
ok = [False for _ in range(n+1)]

def dfs(n):
    ok[n] = True
    for i in arr[n]:
        if not ok[i]: #방문하지 않았다면
            depth[i] = depth[n] + 1
            dfs(i)

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

for i in range(2,n+1): #1,2
    if len(arr[i]) == 1:
        cnt += depth[i]
if cnt % 2 == 0:
    print("No")
else:
    print("Yes")