[python] 백준 30893번: 트리 게임

문제

문제 출처 : https://www.acmicpc.net/problem/30893

트리 게임은 정점 $N$개, 간선 $N-1$개로 이루어진 트리 위에서 진행되는 게임입니다. 각 정점은 $1$ 이상 $N$ 이하의 번호를 하나씩 가집니다.

트리 위에는 $1$개의 말이 있는데, 각 플레이어는 자신의 턴에 간선으로 이어진 인접한 정점으로 말을 옮겨야 합니다. 단, 한 번 방문했던 정점으로는 이동할 수 없으며, 더는 말을 움직일 수 없게 되면 게임이 종료됩니다. 이때 게임 진행 과정에서 한 번이라도 말이 목표 정점 $E$를 방문했다면 선공의 승리이고, 그렇지 못하면 후공의 승리입니다.

기말고사 공부가 너무도 하기 싫었던 태호와 윤아는 트리 게임만 수천 판을 해버렸고, 결국 트리 게임의 최선의 전략을 터득해 버렸습니다. 더는 기말고사 공부를 미룰 수 없었던 태호와 윤아는 마지막 승부를 내기로 했고, 가위바위보를 이긴 윤아가 선/후공 결정권을 가져왔습니다.

이때 윤아가 게임에서 승리하려면 선공, 후공 중 어느 것을 골라야 할까요?

단, 태호와 윤아는 최선의 전략을 이미 알고 있고, 최적의 방법으로 게임에 임한다고 가정합니다.

입력

첫째 줄에 정점의 개수 $N (2≤N≤100,000)$과 말의 시작 정점 $S$, 목표 정점 $E (1≤S, E≤N, S≠E)$가 주어집니다. 다음 $N-1$개의 줄에 걸쳐서 트리의 각 간선이 잇는 두 정점의 번호 $u, v (1≤u, v≤N, u≠v)$가 주어집니다.

출력

윤아가 게임에서 승리하기 위해 선공을 골라야 하면 First를, 후공을 골라야 하면 Second를 출력해주세요.

문제 풀이

접근

• first가 이기는 경우의 수 second가 이기는 경우의 수를 생각해보자.
• 선공이 이기기 위해서는 후공의 턴에 갈 수 있는 노드가 목표노드를 향해 있어야만 한다.
• 후공이 이기는 방법은 그 반대이다.

풀이

1. DFS를 활용하여 시작노드부터 탐색한다.
2. 현재 노드가 목표 노트일 경우 True를 리턴한다.
3. 후공 turn에서 갈 수 있는 노드가 2개 이상이면 False를 리턴한다.
4. 아무것도 해당하지 않는다면 남은 노드들을 탐색하여 하나라도 True가 나오면 True를 리턴한다.

코드

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(x, turn):
    if x == e:
        return True
    visited[x] = 1
    cnt = 0
    for xx in graph[x]:
        if visited[xx] == 0:
            cnt += 1
    if turn % 2 == 0 and cnt > 1:
        return False
    tmp = False
    for xx in graph[x]:
        if visited[xx] != 0:
            continue
        tmp = tmp or dfs(xx, turn + 1)
    return tmp

n, s, e = map(int, input().split())
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 = [0] * (n + 1)
if dfs(s, 1):
    print("First")
else:
    print("Second")

후기

python 에서는 재귀를 1000번으로 제한한다. dfs를 풀때는 대부분 sys.setrecursionlimit(10 ** 7)이 필요할 것 같다.
게임 이론도 그렇고 크게 어렵지는 않았다. (채점하는데 시간이 엄청 오래 걸린다)