트리의 모든 리프 노드에는 말이 정확히 하나씩 놓여있습니다. 이제a와b가 서로 번갈아가며 한 번에 말을 하나씩 옮기는 게임을 하려고 합니다. 게임의 방식은 다음과 같습니다.
차례가 되면 존재하는 말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 말을 옮깁니다.
한 노드에는 여러개의 말이 존재할 수 있습니다.
루트 노드에 말이 도착한다면 즉시 그 말을 제거합니다. 여기서 루트 노드는1번 입니다.
더 이상 옮길 말이 없는 상태에서 차례가 돌아온 사람의 패배입니다.
a가 먼저 시작하며a,b모두 최선을 다해 게임을 진행한다고 했을 때, 주어진 트리에서a가 승리할 수 있는지 판단하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에 트리 노드의 개수N이 주어집니다.
두 번째 줄부터N개의 줄에 각각 걸쳐 간선으로 연결된 두 개의 노드 번호가 공백을 두고 차례대로 출력됩니다.
2≤N≤100000
1≤트리의 노드 번호≤N
출력 형식
주어진 트리에서a가 승리할 수 있다면1을, 승리할 수 없다면0을 출력하세요.
입출력 예제
예제1
입력:
5 1 2 1 3 3 4 4 5
출력:
0
이 문제는 시뮬레이션 처럼 푸는 것이 아니라 모든 리프노드와 루트노드까지의 거리를 모두 구해 그 합이 홀수 인지 짝수 인지 알아보는 문제이다.
루트노드와 모든 리프노드의 말까지 거리의 합이 S라고 하자 a가 한턴 진행하면 말 하나가 위로 올라가고 S는 -1만큼 줄어든다. b가 한턴 진행하면 어떤 말을 하나 선택하든 역시 말 하나가 위로 올라가고 S는 -1만큼 줄어든다. 이러한 과정을 반복하다가 S가 최초로 0이 되는 턴에 말을 움직여야 하는 사람이 진다.
-> 따라서 루트노드에서 모든 리프노드까지의 거리를 구해야한다.
import sys
sys.stdin=open('input.txt', 'r')
sys.setrecursionlimit(100_000)
# DFS를 통해 리프노드와 리프노드의 깊이를 탐색합니다.
def DFS(x):
global S
is_leaf=True
for y in graph[x]:
if visited[y]: # 이미 방문한 노드는 스킵합니다.
continue
is_leaf=False # 하나라도 자식 노드가 있다면 리프 노드가 아닙니다.
visited[y]=True # 방문 체크
depth[y] = depth[x]+1 # root로부터의 거리를 갱신합니다.
DFS(y)
if is_leaf: # 리프노드라면, 해당 노드의 깊이를 더합니다.
S += depth[x]
if __name__=="__main__":
n = int(input())
graph=[[] for _ in range(n+1)]
visited = [False]*(n+1)
depth = [0]*(n+1) # 루트노드와 리프노드간의 깊이(거리)를 저장
for _ in range(n-1):
a,b=map(int, input().split())
graph[a].append(b)
graph[b].append(a)
S=0 # 리프노드 깊이의 총합
root = 1
visited[root]=True
DFS(root) # DFS를 통해 리프노드와 리프노드의 깊이를 탐색합니다.
# 모든 리프노드의 깊이의 합이 짝수인지 홀수인지 판단해 정답을 출력합니다.
if S%2==1:
print(1)
else:
print(0)
