문제 소개
두 명의 플레이어가 번갈아 진행하는 게임의 상태를 하나의 이진 트리(binary tree)로 표현한다고 가정해 보겠습니다. 모든 내부 노드는 0으로 초기화되어 있으며, 리프 노드의 값은 해당 경로가 종료되었을 때 얻게 되는 최종 점수를 나타냅니다.
플레이어 1은 최종 점수를 최대화(maximize)하려고 하고, 반대로 플레이어 2는 최종 점수를 최소화(minimize)하려고 합니다. 플레이어 1은 항상 짝수 레벨(루트를 0번 레벨로 가정)에서 수를 두고, 플레이어 2는 홀수 레벨에서 수를 둡니다. 두 플레이어 모두 최선의 수를 둔다고 가정했을 때, 트리의 각 내부 노드를 결과 점수로 채우는 것이 이 문제의 목표입니다.
예를 들어 입력 트리가 다음과 같다면,
출력 결과는 아래와 같습니다.
알고리즘 접근 방법
핵심 아이디어는 후위 순회(post-order traversal)입니다. 부모 노드의 값은 자식 노드들의 값이 모두 확정된 이후에야 계산할 수 있기 때문에, 재귀 호출로 자식들을 먼저 처리한 뒤 현재 노드의 값을 결정합니다.
helper(root, h, currentHeight)함수를 정의합니다.- 루트가 비어 있으면(null) 그대로 반환합니다.
- 왼쪽 자식과 오른쪽 자식에 대해 각각
helper()를 재귀 호출하며, 이때 깊이는currentHeight + 1로 전달합니다. - 재귀 호출이 돌아온 후, 현재 노드가 리프가 아니라면(
currentHeight < h) 다음 규칙에 따라 값을 채웁니다.- currentHeight가 짝수(플레이어 1 차례): 두 자식이 모두 있으면 자식 값 중 최댓값, 한쪽만 있으면 그 자식의 값을 선택합니다.
- currentHeight가 홀수(플레이어 2 차례): 두 자식이 모두 있으면 자식 값 중 최솟값, 한쪽만 있으면 그 자식의 값을 선택합니다.
height(root)함수를 정의해 트리의 전체 높이를 구합니다. 빈 트리는 0, 그렇지 않으면1 + max(height(left), height(right))를 반환합니다.- 메인 로직에서는 트리의 높이
h를 구한 뒤helper(root, h, 0)을 호출하고, 값이 채워진 루트를 반환합니다.
Python 구현 예제
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def helper(self, root, h, currentHeight):
if not root:
return
# 자식 노드부터 처리 (후위 순회)
self.helper(root.left, h, currentHeight + 1)
self.helper(root.right, h, currentHeight + 1)
if currentHeight < h: # 리프 노드가 아닌 경우만 갱신
if currentHeight % 2 == 0:
# 짝수 레벨: 최대화 플레이어
if root.left and root.right:
root.val = max(root.left.val, root.right.val)
elif root.left:
root.val = root.left.val
elif root.right:
root.val = root.right.val
else:
# 홀수 레벨: 최소화 플레이어
if root.left and root.right:
root.val = min(root.left.val, root.right.val)
elif root.left:
root.val = root.left.val
elif root.right:
root.val = root.right.val
def height(self, root):
if not root:
return 0
return 1 + max(self.height(root.left), self.height(root.right))
def solve(self, root):
h = self.height(root)
self.helper(root, h, 0)
return root
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.val, end=', ')
print_tree(root.right)
ob = Solution()
root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)
print_tree(ob.solve(root))입력
root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)출력
3, 3, -3, -3, -3, 4, 4,동작 원리 살펴보기
예제 트리의 높이는 4입니다(레벨 0~3). 리프 노드인 -3, 4, 3은 원래 값이 그대로 유지되며, 나머지 노드는 아래와 같이 채워집니다.
- 레벨 2의 노드들: 짝수 레벨이므로 최대화 플레이어 차례입니다. 오른쪽 아래 노드는 자식 중 4 하나뿐이므로 4가 되고, 왼쪽 아래 노드는 -3 하나뿐이므로 -3이 됩니다.
- 레벨 1의 오른쪽 노드: 홀수 레벨이므로 최소화 플레이어 차례입니다. 자식 값 -3과 4 중 작은 값인 -3을 선택합니다.
- 레벨 1의 왼쪽 노드(3): 리프 노드이므로 원래 값 3이 그대로 유지됩니다.
- 루트 노드: 짝수 레벨이므로 자식 값 3과 -3 중 큰 값인 3을 선택합니다.
중위 순회(in-order) 방식으로 출력하면 3, 3, -3, -3, -3, 4, 4라는 결과를 확인할 수 있습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다(n은 노드의 개수).
- 공간 복잡도: O(h) — 재귀 호출 스택의 최대 깊이는 트리의 높이 h에 비례합니다.
Min-Max 게임 트리 채우기는 게임 이론의 미니맥스 원리를 트리 순회로 구현하는 대표적인 문제로, 체스·오목과 같은 완전 정보 게임 AI의 핵심 기반이 되는 알고리즘이니 꼭 익혀두시길 바랍니다.