BLOCKGAME (중, p. 344)

문제#

어떻게 풀었나?#

게임판의 상태에 따라 승부는 이미 결정된 것이나 다름이 없다. 그러므로 어떤 플레이어 차례인지는 중요하지 않고, 현재 게임판의 상태를 잘 표현하기만 하면된다. 그래서 게임판을 bit로 표현했고, 게임판이 5x5이므로 총 25칸이어서 상태공간 배열을 [1«25]로 잡았다. 그리고 메모리 제한 때문에 int를 쓰는경우 128MB가 나와서 char로 표현하여 32MB로 줄였다.

이제 모든 경우의 수를 다 볼 수 있는 dfs를 만들었다. 둘 수 있는 공간이 있는지 보고, 그런 공간이 있다면 블록을 올려두는 식이다.

1<<25는 3210241024이므로 3200만 정도 된다. 각 상태에 대한 답이 하나만 존재하고, memoization을 활용하기 때문에 한번 계산된 상태공간은 다시 계산하지 않으므로 시간복잡도도 O(3210241204)이다. 혹시 시간초과가 날 수 있지 않을까 해서 가지치기를 좀 했는데, 블럭 6개(회전한 경우를 모두 포함해서 6개가 됨)중에 특정 블럭을 놓을 수 없는 경우, 다른 블럭이 가능한지 보지 않아도 되는 경우가 있어서 그 경우를 건너뛰게 했다. 전부다 건너 뛴건 아니고, 적당히 대충 몇개 건너 뛰는 식으로 구현했다.

코드는 아래와 같다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
const signed char LOSE = 0;
const signed char WIN = 1;
vector<string> board;
signed char dp[1<<25];
struct Coord{
    int x,y;
    Coord(){}
    Coord(int x, int y):x(x),y(y) {}
};
vector<vector<Coord>> blks = {
    {{0,1}},
    {{0,1},{1,1}},
    {{0,1},{1,0}},
    {{1,0}},
    {{1,0},{1,1}},
    {{1,0},{1,-1}}
};
bool CanPutDownBlk(int bit, int x, int y, int k) {
    for(int i=0; i<blks[k].size(); i++) {
        int nx = x+blks[k][i].x;
        int ny = y+blks[k][i].y;

        if(nx<0||ny<0||nx>=5||ny>=5) return false;
        if(bit & (1<<(nx*5+ny))) return false;
    }
    return true;
}
void TogBlk(int & bit, int x, int y, int k) {
    bit ^= (1<<(x*5+y));
    for(int i=0; i<blks[k].size(); i++) {
        int nx = x+blks[k][i].x;
        int ny = y+blks[k][i].y;
        bit ^= (1<<(nx*5+ny));
    }
}
signed char dfs(int bit, int cnt) {
    if(dp[bit]>=0) return dp[bit];
    else if(cnt<=1) return LOSE; //lose
    signed char & ret = dp[bit];

    signed char tmp;
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++) {
            if(bit&(1<<(i*5+j))) continue;
            for(int k=0; k<6; k++) {
                if(CanPutDownBlk(bit,i,j,k)) {
                    TogBlk(bit,i,j,k);
                    tmp = dfs(bit,cnt-blks[k].size());
                    TogBlk(bit,i,j,k);
                    if(tmp == LOSE) return ret=WIN;
                }
                else {
                    if(k==0) k=2;
                    else if(k==3) break;
                    else if(k==2) break;
                }
            }
        }
    }
    return ret=LOSE;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    board.resize(5);
    while(tc--) {
        memset(dp,-1,sizeof(dp));
        int cnt=0, bit=0;
        for(int i = 0; i < 5; i++) {
            cin >> board[i];
            for(int j = 0; j < 5; j++) {
                if(board[i][j] == '#') {
                    cnt++;
                    bit |= (1 << (i * 5 + j));
                }
            }
        }

        // State s{board, 0};
        if(dfs(bit, 25 - cnt) == WIN) puts("WINNING");
        else puts("LOSING");
    }
    return 0;
}