⚠️ 문제
https://www.acmicpc.net/problem/15900
🔐 풀이
문제에서 모든 게임말은 리프 노드에 존재하고, 각 차례에 게임말을 부모 노드로 옮겨야하는데 더 이상 옮길 말이 없으면 게임이 끝납니다. 이때 먼저 게임을 시작한 "성원"이가 게임을 이기기 위해서는 말을 움직일 수 있는 총 횟수가 홀수여야 합니다. 말을 움직일 수 있는 총 횟수는 각 리프노드까지의 depth를 모두 더한 것과 같기 때문에 이를 구해 홀수인지 확인하면 성원이가 게임을 이길 수 있는지 알 수 있습니다.
그래프를 BFS로 탐색하며 리프 노드를 찾는데, queue에 depth도 함께 저장하며 진행합니다.
현재 노드에서 더 이상 탐색할 자식 노드가 없다면 리프 노드이기 때문에 그때까지의 depth를 총 횟수에 저장합니다.
탐색이 끝나면 모든 리프 노드까지의 depth를 알 수 있기 때문에 이때 총 횟수가 홀수인지 확인하면 됩니다.
🧑🏻💻 코드
import sys
from collections import deque
N = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(N-1):
f, s = map(int, sys.stdin.readline().split())
graph[f].append(s)
graph[s].append(f)
dq = deque()
dq.append((0, 1))
visited[1] = True
depth_cnt = 0
# BFS로 탐색
while dq:
now_depth, now_node = dq.popleft()
# 리프 노드인지 확인하기 위한 변수
# 만약 더 이상 탐색할 자식 노드가 없으면 리프 노드
isLeaf = True
for next_node in graph[now_node]:
if not visited[next_node]:
isLeaf = False
visited[next_node] = True
# 자식 노드 탐색하며 depth + 1
dq.append((now_depth+1, next_node))
# 리프 노드면 지금까지의 depth를 총 횟수에 저장
if isLeaf:
depth_cnt += now_depth
if depth_cnt % 2 == 1:
print("Yes")
else:
print("No")