무식하게 풀기(Brute force) - 3. 게임판 덮기

문제 : 게임판 덮기 (난이도 下)

 

https://algospot.com/judge/problem/read/BOARDCOVER

 

위 문제를 '무식하게' 풀어보자.

 

문제 분석

 

L자 모형을 회전해서 나오는 모양들은 다음과 같다.

 

L 모형의 회전

게임판 중 맨 좌측 상단 빈칸부터 재귀 호출을 시작한다.

A, B, C, D 네타입의 도형을 넣으면서 재귀를 수행하면 된다.

 

이 문제는 답이 항상 0인 사례가 존재한다.

 

1. 높이가 1인 경우

2. 빈칸 (흰색 칸)이 3의 배수가 아닌 경우

 

기저사례는 모든 칸을 다 채웠을 때이다.

 

구현

 

using namespace std;

//주어진 칸을 덮을 수 있는 네가지 방법.
//상대적인 위치 (dy, dx)
//별표시를 시작 위치로 잡았다.
const int cover_type[4][3][2] = {
	{{0,0},{1,0},{1,1}}, //A
	{{0,0},{0,1},{1,0}}, //B
	{{0,0},{0,1},{1,1}}, //C
	{{0,0},{1,0},{1,-1}}, //D
};

//delta 역할에 주목하자.
bool set(vector<vector<int>>& board, int y, int x, int type, int delta)
{
	bool check = true;
	for (int i = 0; i < 3; i++)
	{
		const int next_y = y + cover_type[type][i][0];
		const int next_x = x + cover_type[type][i][1];
		//벡터 사이즈 주의 H : board의 사이즈, L : board[i]의 사이즈.
		if (next_y < 0 || next_y >= board.size() || next_x < 0 || next_x >= board[0].size())
			check = false;
		//set함수의 핵심.
		//delta값을 더함으로써 초기화와 판단을 할 수 있다.
		else if ((board[next_y][next_x] += delta) > 1)
			check = false;
	}
	return check;
}

int fillBoard(vector<vector<int>> &board)
{
	//채우지 않은 칸중 가장 좌상단칸을 찾는다.
	int y = -1, x = -1;
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[i].size(); j++)
		{
			if (board[i][j] == 0)
			{
				y = i;
				x = j;
				break;
			}
		}
		//큰 for문 탈출문 
		if (y != -1) break;
	}

	//base case : 모든 칸을 채우면 1을 반환.
	if (y == -1) return 1;

	int ret = 0;

	for (int type = 0; type < 4; type++)
	{
		if(set(board, y, x, type, 1))
			ret += fillBoard(board);
		//덮었던 블록 복구
		set(board, y, x, type, -1);
	}
	return ret;
}

int main()
{
	int C, H, W;
	cin >> C;
	while (C--)
	{
		cin >> H >> W;
		vector<vector<int>> board(H, vector<int>(W,0));
		int white_num = 0;
		//# -> 1, . -> 0
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				char tmp;
				cin >> tmp;
				if (tmp == '#') board[i][j] = 1;
				else
				{
					white_num++;
				}
			}
		}
        
		//항상 0인 사례
		if (H == 1 || white_num % 3 != 0)
		{
			cout << white_num << "0" << '\n';
			continue;
		}
        
		int cnt = fillBoard(board);
		cout << cnt << '\n';
	}
	return 0;
}

 

회고

 

코드를 보면 핵심 부분은 책과 동일한 것을 볼 수 있다.

set함수에서 delta 의 역할이 신선하게 다가왔기에 그대로 사용했다.

 

아이디어는 간단?한 것 같지만 구현하는데 만만치 않다... 

난도 下가 맞는지 싶다..