[백준][Python] 15900번 나무 탈출

15900번: 나무 탈출

 

코드

import sys
sys.setrecursionlimit(10**5)
N = int(input())
tree = [[] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
visit = [0 for _ in range(N+1)]
ans = 0
for _ in range(N-1):
    a,b = map(int,sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

def dep(a):
    visit[a] = 1
    for i in tree[a]:
        if visit[i] == 0:
            depth[i] = depth[a] + 1
            dep(i)

dep(1)
for i in range(2,N+1):
    if len(tree[i]) == 1:   # 리프노드이면
        ans += depth[i]

if (ans % 2 == 0):  # 짝수
    print("No")
else:	# 홀수
    print("Yes")

설명

성원이가 항상 선이기 때문에 움직일 수 있는 말의 총 횟수가 홀수여야 성원이가 이길 수 있다. 그래서 각각의 리프노드의 깊이를 구해 그 합이 홀수인지 짝수인지 확인하면 된다고 생각했다. 

tree 리스트에는 자신과 연결된 노드를 모두 추가해주었다. 만약 연결된 노드가 한개밖에 없으면 부모노드만 존재함을 의미하기 때문에 리프노드이다. (루트는 제외). 따라서 len(tree[i])가 0이면 리프노드이다. 

dfs를 사용하여 모든 노드들의 깊이를 depth리스트에 저장했다. 그리고 리프노드에 해당하는 노드의 깊이만 따로 더해줘서 그 값이 짝수이면 No를 출력하고 홀수이면 Yes를 출력해줬다.

python으로 제출하면 시간초과가 떠서 pypy로 바꿔봤더니 맞았다고 떴다..