[Python] 32645번 동까뚱뽭 게임

https://www.acmicpc.net/problem/32645

---

 

24/11/11

 

 

간단한 게임이론 + 트리 DP문제이다.

---

 

문제 접근 방식:

 

 

DP상태 식을 다음과 같이 정의해보자.

 

DP[i] = $i$번째 노드에서 게임을 진행할 때 누가 이기는 지에 대한 여부

 

DP[i] = 0이라면 후공이 이긴다고 하고, 1이라면 선공이 이긴다고 하자.

 

뭐, 게임이론 많이 한 사람들이라면 스프라그-그런디로 생각해서 mex때릴 수도 있는데, 사실 게임이 하나 뿐이라서 선후공 승패 여부만 따지면 되기 때문에 간단한 게임 DP로도 풀린다.

 

$i$번째 노드에서 밑으로 갈 수 있는 노드를 below라고 한다면, DP[below]가 모두 1이라면, 즉, 선공이 이기는 노드라면 현재 노드는 후공이 이기는 노드(즉, 선공이 지는 노드)가 된다.

 

반면 DP[below]가 존재하지 않거나(즉, 리프노드거나), DP[below] 중 0이 존재한다면, 즉, 선공이 지는 노드가 존재한다면, 선공이 그 쪽 방향으로 움직이면서 선/후공을 바꿀 수 있으므로 DP[i]는 1이 된다.

 

이를 참고해서 트리 DP를 돌리면 충분하다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32645번 동까뚱뽭 게임
# 트리 DP
'''
접근 방법:
dfs돌리기
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500_000)

N = int(input())
DP = [None for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
def dfs(i):
    if DP[i] != None:
        return DP[i]
    visited[i] = 1
    OK = set()
    for below in graph[i]:
        if DP[below] == None and visited[below] == 0:
            DP[below] = dfs(below)
            OK.add(DP[below])
    if len(OK) == 0:
        DP[i] = 0
    elif len(OK) == 1 and 1 in OK:
        DP[i] = 0
    else:
        DP[i] = 1
    return DP[i]
dfs(1)
for i in range(1, N+1):
    if DP[i]:
        print('donggggas')
    else:
        print('uppercut')