[백준] 15900 : 나무탈출 (Python)

출처 : https://www.acmicpc.net/problem/15900

 

문제

평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.

'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.

이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채로 시작한다. 어떤 사람의 차례가 오면, 그 사람은 현재 존재하는 게임말 중 아무거나 하나를 골라 그 말이 놓여있던 노드의 부모 노드로 옮긴다. 이 과정에서 한 노드에 여러 개의 게임말이 놓이게 될 수도 있다. 이렇게 옮긴 후에 만약 그 게임말이 루트 노드에 도착했다면 그 게임말을 즉시 제거한다. 모든 과정을 마치면 다음 사람에게 차례를 넘긴다. 이런 식으로 계속 진행하다가 게임말이 게임판에 존재하지 않아 고를 수 없는 사람이 지게 된다.

성원이를 얕본 형석이는 쿨하게 이 게임의 선을 성원이에게 줘버렸다. 따라서 성원이가 먼저 시작하고 형석이가 나중에 시작한다. 그동안 형석이와 대결을 하면 매번 지기만 했던 성원이는 마음속에 분노가 가득 쌓였다. 이번 대결에서는 반드시 이겨서 형석이의 코를 꺾어주고 싶다. 그래서 게임을 시작하기 전에 게임판의 모양만 보고 이 게임을 이길 수 있을지 미리 알아보고 싶어졌다. 성원이가 이 게임을 이길 수 있을지 없을지를 알려주는 프로그램을 만들어 성원이를 도와주자.

입력

첫째 줄에 트리의 정점 개수 N(2 ≤ N ≤ 500,000)이 주어진다.

둘째 줄부터 N-1줄에 걸쳐 트리의 간선 정보가 주어진다. 줄마다 두개의 자연수 a, b(1 ≤ a, b ≤ N, a ≠ b)가 주어지는데, 이는 a와 b 사이에 간선이 존재한다는 뜻이다.

출력

성원이가 최선을 다했을 때 이 게임을 이길 수 있으면 Yes, 아니면 No를 출력한다.

---

 

아이디어

해당 문제는 특수 그래프 중 하나인, 트리에서의 탐색 문제이다. 요구사항은 쉽게 파악 가능한 문제이므로, 어떤 인사이트가 있는지 자세히 살펴보자.

 

'성원이가 이 게임을 이길수 있을지 없을지를 알려주는 프로그램'

특정 경우의 상황에 대한 경로 등을 묻는 문제가 아니고, 단순히 게임 승리에 대한 여부만 출력하면 된다. 게임말이 존재하는 위치는 단말노드에 존재하므로, 트리 상에서 게임말을 움직여 어떻게 이기는지에 대해 생각해보면 쉽게 해결할 수 있다.

 

게임을 이기는 조건

다음의 예제 입력3번에 대한 사진을 보자.

예제 입력 3번 케이스 시각화

해당 그림을 통해 다음의 설정 내용을 알 수 있다.

• 단말 노드 : {2, 5, 7, 8}
• 게임의 탈출구 : 1번 노드(root)
• Root의 서브 트리 개수 : 3개 {3, 4, 8}

게임을 시뮬레이션 했을 때, 위의 사진을 다음의 사진 같이 서브트리로 나눠서 행동을 관측할 수 있다.

게임 시뮬레이션. 왼쪽 서브트리 -> 오른쪽 마지막 서브트리

• 1번째 서브트리
  • 성원 -> 형석
• 2번째 서브트리
  • 5번 단말노드 : 성원 -> 형석 -> 성원
  • 6번 단말노드 : 형석 -> 성원
• 3번째 서브트리
  • 형석
• 최종 게임말 움직이는 순서
  • 1번째 서브트리 -> 2번째 서브트리 -> 3번째 서브트리
  • (성원 -> 형석) -> (성원 -> 형석 -> 성원 -> 형석 -> 성원) -> (형석)
  • 최종 승자 : 형석

해당 시뮬레이션에서 성원이가 지는 상황을 잘 살펴보면 다음과 같은 규칙을 알 수 있다.

• 성원 -> 형석 : LOSE
• 성원 -> 형석 -> 성원 : WIN

즉, 마지막 게임말을 성원이가 움직여야 게임에서 승리할 수 있는 조건을 알 수 있다. 이를 바탕으로, 다음과 같은 인사이트를 발견할 수 있다.

• 움직이는 순서 = 루트 ~ 단말 노드까지의 거리
• 루트 ~ 각 단말 노드까지의 거리 총합을 N이라 하자.
  • N이 홀수라면, 성원 -> 형석 -> 성원이므로, 성원 승리
  • N이 짝수라면, 성원 -> 형석이므로, 형석 승리

이를 이용하여, 프로그램 설계를 구현할 수 있다.

 

DFS vs BFS

게임 승리의 여부만 물어보는 문제이므로, 어느 탐색 기법을 써도 상관은 없다. 다만, 통상적으로 탐색 평균 시간이 DFS가 빠르기 때문에, 필자는 DFS를 선택하였다.

 

단말 노드를 체크하는 방식

단말 노드의 특징은 '왼쪽 및 오른쪽 서브트리가 존재하지 않는다.' 이다. 트리를 2차원 행렬로 저장하게 된다면 다음 표와 같이 된다.

예제 입력 3번 케이스의 트리를 저장한 2차원 행렬 : graph

빨간색 노드를 보면 알 수 있다. 2번 노드와 5번 노드는 단말노드이고, 각 행들이 가지고 있는 간선은 1개밖에 없다. 이를 통해, 루트~각 노드들 까지의 거리를 구했다면, 단말 노드에 해당되는 거리들만 따로 누적 저장하면 된다.

 

코드 주의 사항

다양한 오류의 흔적..

출력 내용 확인

'Yes', 'No'를 'YES', 'NO'라고 하는 실수를 범하지 말자..

 

런타임 에러 Recursion_Error

해당 문제에서 정점의 최대 개수는 50만이다. 즉, DFS 탐색의 호출 최대 범위는 50만까지 가능하다는 의미이므로, Python 상에서 호출 깊이를 50만 이상으로 설정해줘야 한다는 것을 주의하자.

 

정답 코드

# https://www.acmicpc.net/problem/15900
# 나무 탈출
# 트리, 그래프탐색, dfs

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

def dfs(root):
    visited[root]=1
    for next_node in graph[root]:
        if not visited[next_node]:
            paths[next_node]=paths[root]+1 # 루트로부터 해당노드까지의 거리 갱신
            dfs(next_node)


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

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

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])

Python3는 시간 초과 가능성 있으므로, PyPy3로 제출.