Treejin's Note

문제 설명

• 5x5크기의 게임판에서 진호와 현환이는 번갈아가며 하나씩 게임판에 블럭을 놓는다.
• 블럭은 3칸짜리 L모양 블럭과 2칸짜리 블럭이 있다.
• 블럭은 항상 게임판의 줄에 맞춰 놓아야 한다.
• 블럭은 자유롭게 뒤집거나 회전하기가 가능하다.
• 더 올려놓을 수 있는 블록이 없게 되면 마지막에 올려놓은 사람이 승리한다.

=> 진행 중인 게임판이 주어질 때, 이번 차례인 사람이 승리할 수 있는 방법이 있는지 출력하기

문제 풀이

문제 풀이

이 문제는 이기는 방법이 하나라도 있으면 WINNING을 출력할 수 있는 문제이다.

따라서, 블록이 놓여있지 않는 빈 칸을 만나면 해당 칸에 놓을 수 있는 블록의 경우의 수를 전부 수행하고

한 번이라도 이기는 경우가 있다면 연산을 더 수행할 필요 없이 승리함을 반환하면 된다.

메모이제이션

진행 중인 게임판 상황에 대한 결과를 저장하면 중복 계산이 발생했을 때 시간을 단축시킬 수 있다.

이 문제는 5x5로 게임판의 크기가 정해져 있다.

하지만 2차원 배열을 메모이제이션으로 저장하기엔 공간을 너무 많이 차지하므로

비트마스킹을 이용해서 5x5 = 25 각 칸에 한 칸씩에 대한 정보를 저장하도록 하면

1<<25크기의 배열에 메모이제이션을 수행하도록 할 수 있다.

문제 풀이 코드

#include <iostream>
#include <string.h>

using namespace std;

char memo[1 << 25];	// 1 << 25

int game(int map) {
	char& ret = memo[map];
	if (ret != -1)
		return ret;

	ret = 0;

	//    *  1
	// 2  3  4

	for (int i = 0; i < 25; ++i) {
		if (((map >> i) & 1) == 1) {
			int cpmap = map;
			cpmap = cpmap ^ (1 << i);

			bool one = i % 5 != 4 && ((map >> (i + 1)) & 1);
			bool two = i < 20 && i % 5 != 0 && ((map >> (i + 4)) & 1);
			bool three = i < 20 && ((map >> (i + 5)) & 1);
			bool four = i < 19 && i % 5 != 4 && ((map >> (i + 6)) & 1);


			if (one) {
				cpmap = cpmap ^ (1 << (i + 1));				// 가로 2칸

				if (three) {	// 아래 1칸
					cpmap = cpmap ^ (1 << (i + 5));
					int result = game(cpmap);
					if (!result)
						return ret = 1;
					cpmap = cpmap ^ (1 << (i + 5));
				}

				if (four) {	// 아래 우측 대각선 1칸
					cpmap = cpmap ^ (1 << (i + 6));
					int result = game(cpmap);
					if (!result)
						return ret = 1;
					cpmap = cpmap ^ (1 << (i + 6));
				}

				int result = game(cpmap);
				if (!result)
					return ret = 1;
				cpmap = cpmap ^ (1 << (i + 1));
			}

			if (three) {
				cpmap = cpmap ^ (1 << (i + 5));				// 세로 2칸

				if (two) {	// 아래 좌측 대각선 1칸
					cpmap = cpmap ^ (1 << (i + 4));
					int result = game(cpmap);
					if (!result)
						return ret = 1;
					cpmap = cpmap ^ (1 << (i + 4));
				}

				if (four) {	// 아래 우측 대각선 1칸
					cpmap = cpmap ^ (1 << (i + 6));
					int result = game(cpmap);
					if (!result)
						return ret = 1;
					cpmap = cpmap ^ (1 << (i + 6));
				}

				int result = game(cpmap);
				if (!result)
					return ret = 1;
				cpmap = cpmap ^ (1 << (i + 5));
			}

			cpmap = cpmap ^ (1 << i);
		}
	}

	return ret;
}

int main() {
	int C;
	cin >> C;
	memset(memo, -1, sizeof(memo));
	for (int tc = 1; tc <= C; ++tc) {
		int map = 0;
		for (int i = 0; i < 5; ++i) {
			char row[6];
			cin >> row;
			for (int j = 0; j < 5; ++j) {
				if (row[j] == '.')
					map = map | (1 << (i * 5 + j));
			}
		}
		int result = game(map);
		cout << (memo[map] ? "WINNING" : "LOSING") << endl;
	}
	return 0;
}