[Algospot] 게임판 덮기 (문제 ID : BOARDCOVER)

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

 

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

 

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

---

완전 탐색으로 해결이 가능하다. 우선 빈 공간이 3의 배수여야 하므로 빈공간의 넓이를 구한 후 3으로 나눠지지 않으면 틀렸다고 처리한다. 그 후는 PICNIC 문제와 마찬가지로 제일 왼쪽 상단부터 빈 공간이 있는지 확인한 후 빈 공간에 네 가지의 방법으로 블럭을 채울 수 있는지 확인한다. 4가지 타입으로 각각 타일을 채웠을 때 해당 값이 1을 넘으면 블럭을 놓을 수 없는 경우기 때문에 다시 블럭을 제거한 후 다음 방식으로 넘어간다. 재귀를 모두 마친 후의 전역 변수 res값이 블럭을 채울 수 있는 결과값이 된다.

이제와 확인해보니 문제를 급하게 푸느라 함수 이름을 bfs라 했는데 bfs 방식은 아니니까 헷갈리지 않도록 하자.

 

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

C++ 코드 : 

#include <iostream>
#include <memory.h>
#include <string>
using namespace std;
int p[31][31]; //p[i][j] = 1이면 벽, 0은 빈 공간
int C, H, W;
int res;
int blockType[4][3][2] = {
	{{0,0},{1,0},{0,1}},
	{{0,0},{0,1},{1,1}},
	{{0,0},{1,0},{1,1}},
	{{0,0},{1,0},{1,-1}}
};
void bfs()
{
	int x = -1, y = -1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (p[i][j] == 0) {
				x = i, y = j;
				break;
			}
		}
		if (x != -1) break;
	}
	if (x == -1) {
		res++;
		return;
	}
	for (int i = 0; i < 4; i++) {
		bool check = true;
		for (int j = 0; j < 3; j++) {
			int nx = x + blockType[i][j][0];
			int ny = y + blockType[i][j][1];
			if (nx < 0 || ny < 0 || nx >= H || ny >= W) {
				check = false;
				continue;
			}
			if ((p[nx][ny] += 1) > 1) check = false;
		}
		if(check==true) bfs();
		for (int j = 0; j < 3; j++) {
			int nx = x + blockType[i][j][0];
			int ny = y + blockType[i][j][1];
			if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
			p[nx][ny] -= 1;
		}
	}
}

int main()
{
	cin >> C;
	while (C--) {
		memset(p, 0, sizeof(p));
		cin >> H >> W;
		int spaceCnt = 0; //빈공간의 크기
		res = 0;
		for (int i = 0; i < H; i++) {
			string str;
			cin >> str;
			for (int j = 0; j < W; j++) {
				if (str[j] == '#') p[i][j] = 1;
				else {
					spaceCnt++;
					p[i][j] = 0;
				}
			}
		}
		if (spaceCnt % 3 != 0) {
			cout << "0\n";
			continue;
		}
		bfs();
		cout << res << "\n";
	}
}