백준 15900 나무 탈출(with Python)

어떤 문제?

제목에 적힌 문제입니다.
해당 문제는 DFS로 풀었습니다.

내가 작성한 Solution

문제에서 생각해볼 점

• 처음에 문제를 제대로 이해하지 못해서 어떤 사람이 선택한 말을 상대방이 건드릴 수 없다고 생각하고 접근을 했습니다.

• 문제 의도를 정확하게 해석하지 않아서 엄청 어렵게만 느껴졌었는데 제대로 방향을 잡고 다시 푸니 정말 금방 풀 수 있었습니다.

• 해당 문제는 결국 root node $\rarr$ leaf node 거리 합이 홀수인지 짝수인지를 판별해서 적절하게 출력해주면 됩니다.

• 짝수이면 상대방 차례에서 모든 말이 사라지게 되므로 내가 지게 될 것이고, 반대로 홀수라면 내 차례에서 모든 말이 사라지게 되므로 내가 이기게 됩니다.

• 해당 문제는 input() 을 사용하게 되면 입력 받는데만 시간초과가 발생합니다.

• sys.stdin.readline() 을 활용하면 빠르게 입력을 받을 수 있습니다. (해당 내용을 잘 정리한 글이 있길래 링크를 첨부합니다.)

코드 구현

import sys

N = int(input())

adj = [[] for _ in range(N+1)]
for i in range(N-1):
    n1, n2 = map(int, sys.stdin.readline().rstrip().split())
    adj[n1].append(n2)
    adj[n2].append(n1)

stack = [[1, 0]]
chk = [0] * (N+1)
chk[1] = -1


ls = []

while stack:
    cn, l = stack.pop()
    chk[cn] = 1

    if cn != 1 and len(adj[cn]) == 1:
        ls.append(l)
        continue

    for nn in adj[cn]:
        if chk[nn] == 0:
            stack.append([nn, l+1])

sum_ls = sum(ls)

if sum_ls % 2:
    print('Yes')
else:
    print('No')