[BOJ 16443 // C++] Bolinhas de Gude

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16443번 문제인 Bolinhas de Gude이다.
문제는 아래 링크를 확인하자.

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

16443번: Bolinhas de Gude

하나의 공통된 보드판 위에서 누구의 차례더라도 할 수 있는 움직임이 같으므로 이 게임은 impartial game이고, 따라서 이 문제는 Grundy 수를 이용하여 문제를 해결할 수 있다.

 

다음과 같이 문제의 상황을 분류하자.

 

(1) 초기상태에 한번에 (0,0)으로 옮길 수 있는 구슬이 있는 경우 왕이 이긴다.

 

(2) (1)에 해당하는 구슬이 없는 상황을 생각해보자. 이 때, 각 플레이어는 "(1)에 해당하는 칸으로 말을 움직이지 않는다"는 제약을 갖고 구슬을 움직여야 한다고 가정해도 좋다. (그러한 움직임을 하면 바로 다음 차례에 지기 때문이다.)

이러한 제약사항에서 게임판 위의 각 칸에 대한 grundy 수를 계산할 수 있고, 이를 이용하여 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int grundy[101][101];
int tmp[150];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 1; i <= 100; i++) {
        for (int j = i + 1; j <= 100; j++) {
            memset(tmp, 0, sizeof(tmp));

            for (int k = 1; k < i; k++) {
                if (k == j) continue;
                tmp[grundy[k][j]] = 1;
            }
            for (int k = 1; k < j; k++) {
                if (k == i) continue;
                tmp[grundy[i][k]] = 1;
            }
            int x = i - 1, y = j - 1;
            while (x > 0 && y > 0) {
                tmp[grundy[x--][y--]] = 1;
            }

            int idx = 0;
            while (tmp[idx]) idx++;
            grundy[i][j] = grundy[j][i] = idx;
        }
    }

    int N; cin >> N;
    bool chk = 0;
    int ans = 0;
    while (N--) {
        int x, y; cin >> x >> y;
        if (x == 0 || y == 0 || x == y) chk = 1;
        ans ^= grundy[x][y];
    }

    if (chk || (ans != 0)) cout << 'Y';
    else cout << 'N';
}