[C++]algospot BOARDCOVER

링크 : https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

문제

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

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

입력

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

출력

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

예제

입력	출력
3 3 7 #.....# #.....# ##...## 3 7 #.....# #.....# ##..### 8 10 ########## #........# #........# #........# #........# #........# #........# ##########	0 2 1514

 

문제 풀이

• 왼쪽 위부터 시작해서 블럭을 채운다.
• 블럭을 채울수 있는 모든 경우를 다 해본다. (완전 탐색)
• 블럭 한 조각을 채운 후, 재귀 호출을 통해 나머지 부분을 채워 나간다.
• 재귀 호출이 끝났을 때 채웠던 칸을 다시 비워 블럭을 채우는 4가지 방법을 모두 시도할 수 있도록 한다.
• basecase : 마지막 칸까지 모두 블럭이 찬 경우

개선 사항

☆이 현재위치라고 했을 때 가능한 블럭 모양 4개

한 지점에서 만들 수 있는 블럭의 모양은 12개이지만, 현재 칸보다 왼쪽/위쪽에 있는 블럭은 다 채워져 있다는 것을 전제로 블럭을 왼쪽 위에서부터 시작해서 채우기 때문에 실제로 채울 수 있는 모양은 4개이다. 때문에 12가지 경우를 모두 시도해 볼 필요 없다. 

풀이 코드

// 완전 탐색
// 0ms
#include <iostream>
#include <string.h>
using namespace std;

int board[20][20];
int H, W;
int block[4][2][2] = {
	{{1, 0}, {1, 1}},
	{{1, 1}, {0, 1}},
	{{0, 1}, {-1, 1}},
	{{1, 0}, {0, 1}}
};
int sum = 0;

// 게임판을 벗어나는지 범위 확인하는 함수
int isRange(int x, int y) {
	if (x < 0 || x >= W || y < 0 || y >= H) return 0;
	else return 1;
}
void fillBoard(int b[][20], int y, int x) {
	// 비어있는 다음 칸 찾음
	while (b[y][x] == 1) {
		if (x == W - 1) {
			if (y == H - 1) break;
			y++;
			x = -1;
		}
		x++;
	}
	// basecase
	if (y == H - 1 && x == W - 1) {
		sum++;
		return;
	}
	// 블럭으로 가능한 모든 경우의 수 시도
	for (int i = 0; i < 4; i++) {
		int y1 = y + block[i][0][1];
		int y2 = y + block[i][1][1];
		int x1 = x + block[i][0][0];
		int x2 = x + block[i][1][0];

		if (isRange(x1, y1) == 0 || isRange(x2, y2) == 0) continue;

		// 칸이 모두 비어있는 경우
		if (b[y][x] == 0 && b[y1][x1] == 0 && b[y2][x2] == 0) {
			b[y][x] = b[y1][x1] = b[y2][x2] = 1;
			fillBoard(b, y, x);
			b[y][x] = b[y1][x1] = b[y2][x2] = 0;
		}
	}
}

int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		memset(board, 0, sizeof(board));
		char tmp;
		sum = 0;
		cin >> H >> W;
		for (int j = 0; j < H; j++) {
			for (int k = 0; k < W; k++) {
				cin >> tmp;
				if (tmp == '#') board[j][k] = 1;
			}
		}
		fillBoard(board, 0, 0);
		cout << sum << endl;
	}
}