[Python] 15900번 나무 탈출

✏️ 문제

 

문제 파악

인접리스트를 사용하여 트리를 구성하면 되는 DFS 문제이다.

 

각각의 리프 노드에서 루트까지의 모든 이동 횟수를 계산하여 총 이동 횟수가 홀수면 성원이가 승리하고 짝수면 형석이가 승리한다. 이때 리프 노드에서 루트까지의 이동 횟수는 노드의 깊이와 같으므로 이를 저장할 depth 배열이 따로 필요하다. 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 트리

 

 

코드

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

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
depth = [0] * (n+1)
ans = 0

for _ in range(n-1):
  u, v = map(int, input().split())
  graph[u].append(v)
  graph[v].append(u)

def dfs(v):
  visited[v] = 1

  for neighbor in graph[v]:
    if visited[neighbor] == 0:
      depth[neighbor] = depth[v] + 1
      dfs(neighbor)
  
dfs(1)

for i in range(2, n+1):
  if len(graph[i]) == 1: 
    ans += depth[i]

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

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS