[Algospot] 블록 게임 (문제 ID : BLOCKGAME)

문제

시티빌과 비주얼드에 지친 진호와 현환이는 집에 굴러다니는 블럭들을 모아 새로운 게임을 하기로 했습니다. 5×5 크기의 게임판에서 시작해, 둘이 번갈아 가며 블럭을 하나씩 게임판에 내려놓습니다. 블럭은 L 모양으로 구성된 3칸짜리 블럭과 2칸짜리 블럭이 있으며, 항상 게임판에 있는 줄에 맞춰 내려놓아야 합니다. 블럭들은 서로 겹칠 수 없습니다. 다음 그림은 진행중인 게임판의 모습을 보여줍니다.

그림에서 보이는 바와 같이 각 블록은 자유롭게 뒤집거나 회전해서 올려놓을 수 있습니다. 두 사람이 번갈아가며 블록을 올려놓다가 더 올려놓을 수 없게 되면 마지막에 올려놓은 사람이 승리합니다. 진행 중인 게임판이 주어질 때 이번 차례인 사람이 승리할 수 있는 방법이 있는지를 판단하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다. 각 테스트 케이스는 다섯 줄에 각 다섯 개의 문자로 구성되며, #는 이미 블록이 놓인 칸, 마침표(.)는 블록이 없는 칸을 의미합니다.

 

출력

각 테스트 케이스마다 한 줄을 출력합니다. 이번 차례인 사람이 항상 이길 수 있는 방법이 있다면 WINNING을, 항상 질 수밖에 없다면 LOSING을 출력합니다.

---

또 다른 dp를 이용한 게임 문제이다. 블록판에 두 가지 블록 중 하나를 놓을 때 마지막에 블록을 놓는 사람이 이기는 게임이다.

계속해서 비트마스크를 이용해서 푸는 문제들이 나오는데, 이 방식에 익숙하지 않다보니 문제 푸는 데 어려움이 있다.

 

precalc()에서 게임판이 모두 비어있을 때 놓을 수 있는 모든 블록의 방식을 계산한다. 먼저 L자 블록을 놓는 방법을 구하고 ㅡ자 블록 놓는 방법을 더한다. L자 블록은 5x5 크기의 모든 좌표에 해당하는 정사각형을 만든 후 정사각형의 귀퉁이를 하나씩 제거해서 블록을 만들어 moves에 저장한다.

ㅡ자 블록도 마찬가지로 모두 계산해서 moves에 저장한다. 책의 방식에 의아했던 건, 게임판을 입력받은 후에 놓을 수 있는 블록위치만 저장할 줄 알았는데 모든 위치에 블록을 놓는 걸 보고 의아했다.

 

아무튼 사전 계산을 모두 하고 나면 play함수를 통해 승리 여부를 계산한다. 인자로는 게임판의 상태를 뜻하는 정수형 board를 받는다. 받고나선 아까 미리 계산한 moves에 있는 모든 블록에 대해 이 게임판에 놓을 수 있는지를 확인하고 가능하면 그 게임판과 블록을 다시 play에 호출해서 놓는 방법이 없다면 내가 이긴다는 뜻이므로 res에 1로 저장하고 끝낸다. 만일 놓는 방법이 있다면 이길 수 없다는 뜻이므로 0으로 둔 채 return 한다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/BLOCKGAME.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <bitset>
using namespace std;
int C;
char dp[1 << 25 + 1];
vector<int> moves;
inline int cell(int x, int y) { return 1 << (x * 5 + y); }


//블록을 놓을 수 있는 위치 계산
void precalc()
{
	//L칸 짜리 블록 계산
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			vector<int> cells;
			for (int dx = 0; dx < 2; dx++) 
				for (int dy = 0; dy < 2; dy++) 
					cells.push_back(cell(i + dx, j + dy));
			int square = cells[0] + cells[1] + cells[2] + cells[3];
			for (int k = 0; k < 4; k++) moves.push_back(square - cells[k]);
		}
	}
	//두칸 짜리 블록 계산
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 4; j++) {
			moves.push_back(cell(i, j) + cell(i, j + 1));
			moves.push_back(cell(j, i) + cell(j + 1, i));
		}
	}
}

char play(int board)
{
	char& res = dp[board];
	if (res != -1) return res;
	res = 0;
	for (int i = 0; i < moves.size(); i++) {
		if ((moves[i] & board) == 0) {
			if (!play(board | moves[i])) {
				res = 1;
				break;
			}
		}
	}
	return res;
}
int main()
{
	cin >> C;
	while (C--) {
		memset(dp, -1, sizeof(dp));
		int score = 0;
		precalc();

		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				char tmp;
				cin >> tmp;
				if (tmp == '#') score += cell(i, j);
			}
		}
		if (play(score)) cout << "WINNING" << endl;
		else cout << "LOSING" << endl;
	}
	return 0;
}