백준 15900 : 나무 탈출 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(start):

    visit[start]=True
    for i in Tree[start]:
        if not visit[i]:
            distance[i]=distance[start]+1
            DFS(i)

N=int(input())
Tree=[ [] for _ in range(N+1)]
distance=[0]*(N+1)
visit=[False]*(N+1)
for i in range(N-1):
    a,b=map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)

DFS(1)
answer=0
for i in range(2,N+1): #루트노드는 리프노드가 아니기 때문에 2부터 진행
    if len(Tree[i])==1: # 리프노드라면
        answer+=distance[i]

if answer%2==0:
    print("No")
else:
    print("Yes")

📌 어떻게 접근할 것인가?

모든 리프토드에 말이 있고 서로 번갈아가면서 말을 부모 노드로 옮긴다.
이후 말이 루트노드에 도착하면 말은 사라지고 더이상 말을 옮길수 없는 사람이 지게된다.

여러번 시뮬레이션을 하다 보면 모든 리프노드에서 루트노드까지의 거리의 합이 홀수인지 짝수인지에 따라 결과가 정해진다.

📌 Code

단순히 DFS 를 통해 모든 노드부터 리프노드까지의 거리를 구해준다.
이때 무방향 그래프이기때문에 원소를 2번 추가해준다.

모든 노드에서 리프노드까지의 거리를 구했다면 $Tree$의 길이가 1 , 즉 리프노드인 인덱스에서 거리를 저장한 리스트 $distance$ 값을 answer 에 추가해준다.

만약 answer 값이 짝수라면 $NO$ , 홀수라면 $YES$ 가 된다.

✅ 코드에서 주의해야할 점

• 그래프의 정점은 $N$ 이 아니라 총 $N-1$ 개를 받는다.
• $Tree$의 인덱스 $1$은 루트노드이기 때문에 인덱스 2부터 리프노드인지 탐색한다.