4. DP Technique - 블록 게임(blockgame) 문제

이 문제는 이전에 풀었던 조합게임 문제와 비슷하게 재귀함수를 구현하여 해결할 수 있다.

재귀함수의 각 단계에서는 현재 게임판의 상태를 입력받아 이번에 놓을 블록을 결정하고, 

그 블록을 놓은 후의 게임판의 상태를 다음 재귀호출에 전달하여 해당 블록을 놓았을 때 현재 플레이어가 이길 수 있는지 판단한다.

현재 놓을 블록은 반복문을 통해 모든 경우에 대해서 재귀호출을 해보고 하나라도 다음 플레이어가 지는 경우가 있다면

현재 플레이어가 항상 이길 수 있기 때문에 1 값을 반환한다.

그러나 어떤 블록을 놓아도 항상 다음플레이어가 이긴다면, 현재 플레이어가 무조건 지기 때문에 0 값을 반환한다.

블록에는 3칸짜리 L자모양 블록과 2칸짜리 일자모양 블록이 있다. 

5*5 게임판에 놓을 수 있는 모든 블록을 미리 비트마스크 기법으로 계산하여 저장해두면 재귀함수 구현에 편리하다.

각 게임판의 위치를 (x,y) 좌표로 표시할 때, 각 위치는 x * 5 + y 번 비트로 계산한다.

즉, (2,3) 은 2*5 + 3 = 13 번 비트로 표시하는 것이다.

13번 비트가 1이면 현재 게임판의 (2,3) 위치에 블록이 채워져있는 것이다.

// 블록 게임 문제를 해결하는 다이나믹 프로그래밍 알고리즘

vector<int> moves;  // 게임판의 모든 블록들의 조합

// (x,y) 좌표의 비트 번호를 반환하여 준다.

inline int cell(int x, int y){

return 1 << ( x * 5 + y);

}

// 게임판에 놓을 수 있는 블록들의 위치를 미리 계산한다.

void preCalc(){

// 3칸짜리 L자모양 블록

for(int x = 0; x < 4; x++){

for(int y = 0; y < 4; y++){

vector<int> cells;

for(int dx = 0; dx < 2; dx++)  // 현재 위치와 현재 위치의 오른쪽칸, 아래칸, 오른쪽 아래칸을 cells에 저장

for(int dy = 0; dy < 2; dy++)

cells.push_back( cell(x + dx, y + dy) );

int square = cells[0] + cells[1] + cells[2] + cells[3];  // cells에 저장한 4칸으로 사각형을 만든다.

for(int i = 0; i < 4; i++)

moves.push_back(square - cells[i]);  // 사각형에서 한 칸씩 뺀 L자모양 블록을 moves[]에 저장한다.

}

}

// 2칸짜리 일자모양 블록

for(int x = 0; x < 5; x++){

for(int y = 0; y < 4; y++){

moves.push_back(cell(x, y) + cell(x, y+1));

moves.push_back(cell(y, x) + cell(y+1, x));

}

}

}

char cache[1<<25];

char play( int board){

// 메모이제이션

char& ret = cache[board];

if( ret != -1 ) return ret;

ret = 0;

for(int i = 0; i < moves.size(); i++){

if(moves[i] & board == 0){  // 해당 블록이 게임판에 놓여있지 않으면

if( !play( board | moves[i])){  // 해당 블록을 놓고 난 다음 게임판의 상태에서 다음플레이어가 진다면

ret = 1;  //  현재 플레이어가 항상 이길 수 있다.

break;

}

}

}

return ret;

}