문제 링크
https://www.acmicpc.net/problem/15900
🕒 Python 풀이시간: 20분
import sys
sys.setrecursionlimit(500000)
input=sys.stdin.readline
N=int(input())
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
a,b=map(int,input().split())
graph[a].append(b)
graph[b].append(a)
visited=[False]*(N+1)
answer=0
def dfs(v,layer,visited):
global answer
visited[v]=True
enabled=False
for i in graph[v]:
if not visited[i]:
dfs(i,layer+1,visited)
enabled=True
if not enabled:
answer+=layer
dfs(1,0,visited)
if answer%2==0:
print("No")
else:
print("Yes")🏆 성원이의 승리 비밀! DFS로 나무 게임 해부 🌳
성원이가 이기기 위해서는 나무 말이 도착하는 조건을 보아야한다. 각 말은 부모 노드로 밖에 이동할 수 없기에 최종 노드에 도달하는거까지가 말의 움직임의 전부이고 모든 말의 움직임의 합이 총 게임 턴 수가 된다. 성원이가 이기기 위해서는 이 수가 홀수여야 한다는 것을 알 수가 있다.
그렇기 위해서 DFS로 각 층에서의 이동을 누적시키면 된다. 즉, 각 자식 노드로 뻗으면서 +1씩해주다가 만약에 리프노드라면 즉, 더 이상 갈 수 있는 노드가 없는 상태라면 그 합을 정답에 더해주면 된다. 그렇게 나온 정답이 홀수라면 yes 짝수라면 no다.
이렇게 Python로 백준의 "나무 탈출" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
