스프래그 - 그런디 (Sprague-Grundy) 함수 개요

조합론 게임 이론에서 가장 핵심적인 개념 중 하나는 스프래그 - 그런디 정리입니다. 이 정리는 임의의 공정한 게임 (Impartial Game) 을 니무 게임으로 환원하여 승패를 판별할 수 있음을 보여줍니다. 각 상태에 할당되는 값을 그런디 수 (Grundies Number), 또는 편의상 SG 값이라고 부릅니다.

SG 함수의 정의는 다음과 같습니다:

G(state) = mex({G(next_state) | state -> next_state})

여기서 mex(Minimum Excluded value) 는 주어진 집합에 존재하지 않는 가장 작은 음이 아닌 정수를 의미합니다. 예를 들어, {0, 1, 3} 의 집합이 있다면 mex 값은 2 가 됩니다.

복수의 독립적인 게임이 병렬로 진행될 경우, 전체 게임的局面 의 SG 값은 각 하위 게임의 SG 값들을 이터 (XOR) 합하여 구합니다. 결과 값이 0 이라면 패배 위치 (L-position), 0 이 아니면 승리 위치 (W-position) 로 판단됩니다.

시나리오 1: 비트 개수에 의존하는 게임

일부 문제에서는 숫자의 구체적인 값보다는 내부적으로 설정된 비트 (1 의 개수) 에 따라 상태가 결정되는 경우가 있습니다. 다음과 같은 조건을 가진 게임을 고려해 봅시다:

• 정수 하나를 선택하고 제거한 뒤, 원래 숫자보다 크기가 작으며 비트 포함 관계를 만족하는 7 개의 새로운 정수를 추가한다.
• 더 이상 선택할 숫자가 없을 때 지게 된다.

이 규칙에서 핵심 관찰점은 숫자를 분해하는 과정이 본질적으로 해당 숫자가 가진 설정된 비트 (Set Bits) 의 개수와 관련되어 있다는 것입니다. 즉, $x$ 에서 $x_i$ 를 생성하는 것은 $x$ 의 1 비트들 중 일부를 골라내는 것과 동일하므로, SG 값은 단순히 입력값이 아니라 '1 의 개수'만의 함수로 취급 가능합니다.

모든 가능한 조합을 탐색하여 SG 값을 미리 계산 (Precomputation) 하는 전략을 취할 수 있습니다.

구현 코드 예시 (Precomputation)

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int MAX_BIT = 65;
ull grundy[MAX_BIT];
bool reachable[1 << 20]; // 충분히 큰 크기

// 주어진 비트 개수 n 에서 뽑을 수 있는 다음 상태들의 xor 합을 찾기 위한 탐색
void find_next_states(int limit, int remaining_count, int current_xor, int start_index) {
    if (remaining_count == 0) {
        reachable[current_xor] = true;
        return;
    }
    
    // 중복 순열을 피하기 위해 오름차순으로 인덱스 선택 (조합 접근)
    for (int i = start_index; i < limit && remaining_count > 0; ++i) {
        find_next_states(limit, remaining_count - 1, current_xor ^ grundy[i], i);
    }
}

void initialize_values() {
    grundy[0] = 0; // 종료 상태
    
    cout << "{";
    for (int i = 1; i <= 64; ++i) {
        memset(reachable, 0, sizeof(reachable));
        
        // 현재 비트 수 i 에 대해, 그보다 작은 7 개의 상태를 만들어 xor 합
        find_next_states(i, 7, 0, 0);
        
        // mex 연산 수행
        for (int j = 0; ; ++j) {
            if (!reachable[j]) {
                grundy[i] = j;
                break;
            }
        }
        
        printf("%d:%llu%s\n", i, grundy[i], (i == 64) ? "}" : ",");
    }
}

탐색 시 중복 계산을 방지하기 위해 인덱스를 엄격하게 증가시켜야 합니다. 이는 순열 대신 조합의 개념을 사용하여 시간 복잡도를 대폭 줄이는 기법입니다. 사전 계산된 테이블을 이용하면 실제 게임 처리 시에는 입력된 각 숫자의 비트 개수를 세어 해당하는 SG 값을 찾아 XOR 합만 취하면 됩니다.

시나리오 2: 격자 자르기 게임 (Recursive Memoization)

두 번째 사례로는 직사각형 격자를 자르는 게임이 있습니다. 플레이어는 가로 또는 세로 한 선을 잘라 두 개의 더 작은 직사각형으로 분할합니다. 단, 변의 길이가 1 되는 절삭은 허용되지 않습니다 (또는 특정 승리 조건에 의해 유효하지 않음). 이러한 구조에서는 상태 공간이 $W \times H$ 만큼 존재하며, 깊이 우선 탐색 (DFS) 과 메모이제이션을 결합하여 점근적으로 효율적으로 해답을 구할 수 있습니다.

상태 $(x, y)$ 의 SG 값은 이를 자를 수 있는 모든 가능한 상태들의 SG 값을 XOR 한 것들의 mex 입니다.

구현 코드 예시 (Recursive SG)

#include <bits/stdc++.h>
using namespace std;

int memo_table[205][205];
bool seen_states[100000]; // visited 플래그 용도

// 상태 (r, c) 에 대한 그런디 수를 재귀적으로 계산
int calculate_sg(int r, int c) {
    // 이미 계산된 값이 있으면 반환
    if (memo_table[r][c] != -1) return memo_table[r][c];
    
    // 보석 초기화
    memset(seen_states, 0, sizeof(bool) * (r * c + 100)); 
    
    // 가로로 자르는 경우
    for (int i = 2; i < r - 1; ++i) {
        int val = calculate_sg(i, c) ^ calculate_sg(r - i, c);
        if (val < (int)(sizeof(seen_states) / sizeof(bool))) seen_states[val] = true;
    }
    
    // 세로로 자르는 경우
    for (int i = 2; i < c - 1; ++i) {
        int val = calculate_sg(r, i) ^ calculate_sg(r, c - i);
        if (val < (int)(sizeof(seen_states) / sizeof(bool))) seen_states[val] = true;
    }
    
    // mex 값 찾기
    int result = 0;
    while (result < (int)(sizeof(seen_states) / sizeof(bool)) && seen_states[result]) {
        result++;
    }
    
    return memo_table[r][c] = result;
}

int main() {
    ios::sync_with_stdio(false);
    memset(memo_table, -1, sizeof(memo_table));
    
    int W, H;
    while (cin >> W >> H) {
        if (calculate_sg(W, H) > 0) {
            cout << "WIN\n";
        } else {
            cout << "LOSE\n";
        }
    }
    return 0;
}

이 코드는 전처리 없이 각 쿼리에 대해 필요한 상태만 계산합니다. 배열 초기화에 -1 을 사용하여 방문 여부를 구분하고, 반복되는 서브 문제를 저장함으로써 성능을 최적화했습니다.

시나리오 3: 단일 상태의 디지털 게임

마지막 예시는 여러 개의 게임 요소가 섞이지 않고 하나의 숫자만 다루는 경우입니다. 규칙은 현재 숫자에서 최댓값인 자릿수나 0 이 아닌 최솟값인 자릿수를 뺀다는 것입니다. 이런 종류의 게임은 독립적인 하위 게임의 합집합이 아니므로, 굳이 XOR 합을 계산할 필요 없이 단순한 승리/패배 여부 (boolean) 만으로 상태를 정의해도 충분합니다.

기본 논리는 다음과 같습니다:

• 현재 상태에서 이동 가능한 다음 상태 중 최소 하나라도 패배 상태 (즉, 상대방이 질 수밖에 없는 상태) 가 있다면, 현재 상태는 승리 상태이다.
• 모든 다음 상태가 승리 상태라면, 현재 상태는 패배 상태이다.

구현 코드 예시 (DP Approach)

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1000005;
bool is_winning[MAX_N];

// 숫자 분석: 최대 자리수 및 최소 비 0 자리수 추출
void analyze_digits(int num, int &max_d, int &min_d) {
    max_d = 0;
    min_d = 9;
    int temp = num;
    
    while (temp > 0) {
        int digit = temp % 10;
        if (digit > max_d) max_d = digit;
        if (digit != 0 && digit < min_d) min_d = digit;
        temp /= 10;
    }
    // 안전 조치
    if (min_d == 9) min_d = 0; 
}

void solve() {
    int G;
    if (!(cin >> G)) return;
    
    // DP 초기화 및 계산
    for (int i = 1; i < MAX_N; ++i) {
        int mx, mn;
        analyze_digits(i, mx, mn);
        
        bool can_reach_loss = false;
        // 최대자리수 빼기
        if (mx > 0) {
            if (i - mx >= 0 && !is_winning[i - mx]) can_reach_loss = true;
        }
        // 최소비 0 자리수 빼기
        if (mn > 0 && !can_reach_loss) {
            if (i - mn >= 0 && !is_winning[i - mn]) can_reach_loss = true;
        }
        
        is_winning[i] = can_reach_loss;
    }
    
    for (int k = 0; k < G; ++k) {
        int N;
        cin >> N;
        cout << (is_winning[N] ? "YES" : "NO") << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

단일 경로 게임에서는 복잡한 SG 함수의 수치적 성질 대신, 귀납적으로 승패를 결정하는 불리언 도메인을 사용하면 알고리즘의 복잡성을 낮출 수 있습니다. 이러한 변형들을 통해 다양한 게임 환경에 맞춰 적절한 모델링을 선택하는 것이 중요합니다.