[Python] 15900 나무 탈출

[Silver I] 나무 탈출 - 15900 

[문제 링크](https://www.acmicpc.net/problem/15900)

---

💻 문제 정의

트리의 리프 노드를 부모 노드로 이동한다. 이동하다가 루트 노트로 옮겨지면 즉시 제거된다. 이때 번갈아가면서 리프 노드로 부터 루트 노드로 갈 때, 먼저 시작해서 이기는 경우와 지는 경우를 판별하는 문제이다.

💡 접근 및 설계

문제만 보면 어렵지만, 결국 리프 노드의 개수에 따라 승패가 결정된다. 리프 노드의 개수가 홀수 개면 이기고, 짝수 개면 진다. 이 방식을 이용한다.

✏️ 알고리즘 풀이

graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
paths = [0] * (N+1)

def dfs(n):
    visited[n] = True

    for ix in graph[n]:
        if not visited[ix]:
            paths[ix] = paths[n] + 1
            dfs(ix)

DFS를 이용하여 리프 노드를 찾는다. 루트 노드에서 부터 아래로 깊이 우선 탐색을 진행하면서, 모든 노드의 깊이를 paths에 저장하게 된다.

paths에 저장된 깊이의 길이가 1인 경우, 해당 노드는 리프 노드가 된다.

🗒️ 최종 제출 코드

# 15900 나무 탈출

import sys
sys.setrecursionlimit(10**5*6) # 정점이 50만까지 들어가기에, 호출 깊이가 50만까지 가능해야함.
input=sys.stdin.readline

def dfs(n):
    visited[n] = True

    for ix in graph[n]:
        if not visited[ix]:
            paths[ix] = paths[n] + 1
            dfs(ix)

N = int(input())

graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

paths = [0] * (N+1)
dfs(1)

print('YNeos'[sum(paths[i] for i in range(2,N+1) if len(graph[i])==1)%2==0::2])

---

💭 오늘의 회고

실버 문제임에도 쉽지 않았던 문제였다. 자신있던 그래프 탐색 문제였지만 생각을 떠올리기 쉽지 않았다. 사실 시간 초과의 벽에 막혀서 헤맸던 것 같다. 파이썬에서 DFS 방식은 두 가지 방법으로 구현할 수 있는데, 재귀와 스택을 이용하는 것이다. 처음에는 재귀 방식에 문제가 있다고 생각해서 스택을 활용한 깊이 우선 탐색을 구현하였으나 역시 시간 초과가 나왔고, 결국엔 재귀 방식의 문제보단 리스트 초기화에서 문제가 있었다.