https://www.acmicpc.net/problem/11717
11717번: Wall Making Game
The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t
www.acmicpc.net
전형적인 impartial game으로 스프라그-그런디 정리(Sprague-Grundy Theorm)를 이용하는 것이 첫 번째 아이디어로 떠올라야 한다.
서브 게임을 정의하는 방법을 생각해야 한다.
기본적으로 각 게임판의 상태는 empty, marked, 그리고 wall 셋 중 하나이므로 크기가 w*h인 게임의 상태는 3^(w*h)개의 상태로 나타낼 수 있다. 하지만 이 방법은 공간을 너무 많이 차지하므로 사용할 수 없다.
게임의 초기에는 wall이 없는 상태이다. 어떤 서브게임에 벽을 새우면, 그 벽을 기준으로 네 개의 서브 게임으로 나눠지게 된다. 네 개의 서브 게임 모두 직사각형 영역이고 게임 안에 벽이 존재하지 않는다. 여기에서 각각의 서브 게임을 그 서브 게임의 공간으로 정의할 수 있다. 서브 게임이 사용하는 공간(벽으로 둘러싸인 공간)을 ((x1, y1), (x2, y2))로 정의하면, 전체 서브 게임의 수는 H^2 * W^2에 바운드된다.
각 서브게임에서 벽을 새울 수 있는 경우의 수는 H*W에 바운드되므로 전체 시간 복잡도는 O(H^3 * W^3)이다. 메모이제이션을 하여 하나의 서브 게임을 여러 번 반복해서 풀지 않도록 한다.
벽을 세울 수 있는 하나의 경우에 대해, 네 개의 서브게임으로 나뉘게 된다. 네 개의 서브 게임의 mex값을 xor을 하여 현 상태의 그런디 수(grundy number)를 구한다. 모든 경우(상태)에 대한 그런디 수의 집합 G를 구하면, 원래 게임의 그런디 수 mex(G)를 구할 수 있다.
스프라그-그런디 정리
https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
Sprague–Grundy theorem - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Every impartial game position is equivalent to a position in the game of nim In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the norma
en.wikipedia.org
'problem solving' 카테고리의 다른 글
| BOJ 1031 스타대결 (0) | 2022.02.26 |
|---|---|
| BOJ 24231 해석 (0) | 2022.02.20 |
| BOJ 10531 Golf Bot (FFT) (0) | 2022.01.23 |
| BOJ 6171 땅따먹기 (볼록껍질 최적화) (0) | 2022.01.22 |
| BOJ 17429 국제 메시 기구 (0) | 2022.01.21 |