Grundy 값과 mex로 푸는 카드 뒤집기 게임

카드 뒤집기 게임

목표 : 연속으로 배치된 카드 중 인접한 2개의 카드가 앞(1)일 때 뒤(0)로 뒤집는 게임이다.
이 게임에서 내가 반드시 승리할 수 있는지 여부를 출력한다.

해결방법 : 연속된 1의 구간을 분리해 메모이제이션을 활용해 풀었다.

• 연속된 구간 분리
  카드 배열에서 연속된 1의 구간(예: [1, 1, 1, 1] → 길이 4)을 분리한다.

• 가능한 이동과 구간 분할
  각 구간에 대해, 인접한 1 두 개를 뒤집는 모든 가능한 이동을 고려한다.
  한 번의 이동은 해당 구간을 두 개의 부분 게임으로 분할한다.

  • 예를 들어, 길이 n인 연속 1에서 인덱스 i와 i+1의 1을 뒤집으면, 왼쪽 부분은 길이 i, 오른쪽 부분은 길이 n−i−2가 된다.

• Grundy 값과 XOR 연산
  두 부분 게임은 독립적이며, 이들의 Grundy 값의 XOR 연산 결과가 해당 이동의 결과값이 된다.
  모든 가능한 이동 결과들 중 집합에 포함되지 않은 가장 작은 음이 아닌 정수(mex)를 구하면,
  이것이 길이 n인 구간의 Grundy 값이 된다.

• 승패 판정
  모든 구간의 Grundy 값을 XOR 연산으로 누적한 결과가 0이 아니면, 선공(내가) 반드시 승리할 수 있다.

import java.util.*;

class Solution {
    // 메모이제이션을 위한 캐시: 각 구간 길이에 대한 Grundy 값을 저장
    Map<Integer, Integer> memo = new HashMap<>();
    
    public boolean solution(int[] cards) {
        // 연속된 1의 구간(블록) 길이를 저장할 리스트
        List<Integer> list = new ArrayList<>();
        int cnt = 0;
        for (int card : cards) {
            if (card == 1) {
                cnt++;
            } else {
                if (cnt > 0) {
                    list.add(cnt);
                    cnt = 0;
                }
            }
        }
        // 배열 끝에 남은 1의 구간 처리
        if (cnt > 0) list.add(cnt);
        
        int nimSum = 0;        
        for (int size : list) {
            nimSum ^= grundy(size);
        }
        
        // 전체 nimSum이 0이 아니면 선공 승리 전략 존재
        return nimSum != 0;
    }
    
    // grundy 메서드: 길이 n인 1의 연속 구간에 대한 Grundy 값을 계산
    int grundy(int n) {
        // 기저 조건: n이 1 미만이면 움직일 수 없으므로 Grundy 값은 0
        if (n < 2) return 0;
        if (memo.containsKey(n)) return memo.get(n);
        
        // 가능한 이동 결과의 Grundy 값을 저장할 집합
        Set<Integer> set = new HashSet<>();
        
        // 가능한 모든 이동: 인접한 두 개의 1을 뒤집는 모든 경우
        for (int i = 0; i <= n - 2; i++) {
            int left = grundy(i);              // 왼쪽 부분의 Grundy 값
            int right = grundy(n - i - 2);       // 오른쪽 부분의 Grundy 값
            set.add(left ^ right);              // XOR 연산 결과 저장
        }
        
        // mex 계산: set에 없는 가장 작은 음이 아닌 정수
        int mex = 0;
        while (set.contains(mex)) mex++;
        
        memo.put(n, mex);
        return mex;
    } 
}

❓ Grundy 값이란

그룬디 값(Grundy value) 은 게임의 한 위치를 Nim 게임의 힙 크기처럼 표현한 전략적 수치입니다. 어떤 게임 상태의 그룬디 값이 k라면, 해당 상태는 크기k의 Nim 힙과 같은 전략적 가치를 가진다는 의미입니다.

Sprague-Grundy 정리에 따르면, 모든 독립적인 게임의 Grundy 값을 XOR한 결과(nim-sum)를 통해 전체 게임의 승패를 결정할 수 있습니다.

• nim-sum = 0 → 패배 상태
• nim-sum ≠ 0 → 승리 전략 존재

❓ mex(Minimum Excludant)란

mex는 집합에 포함되지 않은 가장 작은 음이 아닌 정수입니다.
예를 들어, 집합 {0,1,3}의 mex는 2가 된다.

• Grundy 값 계산에의 적용
  현재 게임 상태에서 가능한 모든 다음 상태들의 Grundy 값을 구하면, 이들의 집합이 만들어진다.
  현재 위치의 그룬디 값은 바로 이 집합에서 존재하지 않는 가장 작은 값(mex)을 취한다.
  이는 “어떤 수를 만들 수 없다”라는 논리에 기반하며, 게임 이론에서 매우 중요한 역할을 한다.

왜 mex를 사용하는가?
그룬디 값은 가능한 모든 이동의 결과에 대해 동일한 전략적 가치를 가지도록 하는 수치이다.
만약 어떤 상태에서 가능한 이동들의 그룬디 값이 {0,1,3}라면, 현재 상태는 이 집합에 없는 가장 작은 수인 2를 갖게 된다. 이러한 방식은 Nim 게임의 힙 크기를 결정하는 것과 동일한 원리로,
각 부분 게임의 상태를 단순화하여 전체 게임의 승패를 결정할 수 있게 해준다.

결론

이 문제의 유형은 Combinatorial Game Theory(조합 게임 이론)라는 유형이다. 정확히 이 이론을 깊이 공부하진 않았지만, 이번 문제는 Combinatorial Game Theory(조합 게임 이론)의 전형적인 적용 예로, Grundy 값과 mex 개념만 이해해도 충분히 풀 수 있었다. 카드 뒤집기 게임 문제를 Sprague-Grundy 정리와 그룬디 값, 그리고 mex 개념을 활용하여 해결하는 방법을 소개했다. 연속된 1의 구간을 독립적인 하위 게임으로 분할하고, 각 구간의 그룬디 값을 계산한 후 전체 게임의 nim-sum을 XOR 연산으로 누적하여 승패를 판별하는 방식은 복잡한 게임 문제를 보다 단순한 Nim 게임 문제로 변환하는 강력한 도구임을 알 수 있다.