Treejin's Note

문제 설명

• 세로 H, 가로 W 크기의 게임판이 주어진다.
• 게임판은 검은 칸과 흰 칸으로 구성된다.
• 흰 칸 영역을 3칸짜리 ㄴ자 모양의 블록으로 덮고자 한다.

=> 모든 흰 칸을 덮을 수 있도록 블록을 배치하는 경우의 수를 출력하기

문제 풀기

이 문제는 전체 칸을 방문하면서, 흰 칸에서 ㄴ자 블록을 배치하는 코드를 구현해야 한다.

그 때,

1. 흰 칸에만 블록이 들어가도록 해야한다.

2. 전체를 돌았을 때 흰 칸이 남지 않아야 한다.

그러므로 왼쪽 상단에서 우측 하단까지 전체 칸을 방문하는데, 흰 칸을 만나면 거기서 배치할 수 있는 모양의 블록을 배치해주면 된다.

블록은 다음과 같은 4가지 경우로 놓을 수 있다.

이 4가지 경우에 해당하지 않을 경우, 전체 흰 칸을 채울 수 없으므로 더 진행할 필요가 없다.

또한 ㄴ블록은 3칸으로 이루어져 있는데,

전체 흰 칸의 개수가 3의 배수가 아니라면 블록을 놓아볼 필요도 없이 전부 채울 수 없으므로 0을 반환한다.

문제 풀이 코드

#include <iostream>
#include <string>

using namespace std;

int C, h, w;
char map[22][22];

int putBlock(int r, int c) {
	if (r > h) {
		return 1;
	}

	// 다음 좌표 값 계산
	int nextR, nextC;
	if (c == w) {
		nextR = r + 1;
		nextC = 0;
	}
	else {
		nextR = r;
		nextC = c + 1;
	}

	int cnt = 0;

	// 흰 칸인 경우
	if (map[r][c] == '.') {
		if (map[r][c+1] == '.' && map[r + 1][c + 1] == '.') {	// 오른쪽, 오른쪽아래
			// 블록 놓기
			map[r][c + 1] = '#';
			map[r+1][c+1] = '#';
			map[r][c] = '#';
			cnt += putBlock(nextR, nextC);
			// 블록 되돌리기
			map[r][c + 1] = '.';
			map[r + 1][c + 1] = '.';
			map[r][c] = '.';
		}
		if (map[r + 1][c] == '.' && map[r + 1][c + 1] == '.') {	// 아래, 오른쪽아래
			map[r+1][c] = '#';
			map[r + 1][c + 1] = '#';
			map[r][c] = '#';
			cnt += putBlock(nextR, nextC);
			map[r+1][c] = '.';
			map[r + 1][c + 1] = '.';
			map[r][c] = '.';
		}
		if (map[r + 1][c] == '.' && map[r + 1][c - 1] == '.') {	// 아래, 왼쪽아래
			map[r + 1][c] = '#';
			map[r + 1][c - 1] = '#';
			map[r][c] = '#';
			cnt += putBlock(nextR, nextC);
			map[r + 1][c] = '.';
			map[r + 1][c - 1] = '.';
			map[r][c] = '.';
		}
		if (map[r + 1][c] == '.' && map[r][c + 1] == '.') {	// 아래, 오른쪽
			map[r + 1][c] = '#';
			map[r][c + 1] = '#';
			map[r][c] = '#';
			cnt += putBlock(nextR, nextC);
			map[r + 1][c] = '.';
			map[r][c + 1] = '.';
			map[r][c] = '.';
		}
		
		return cnt;
	}

	// 검은 칸인 경우
	return putBlock(nextR, nextC);
}

int main() {
	cin >> C;
	for (int tc = 0; tc < C; ++tc) {
		cin >> h >> w;
		// 테두리 # 처리
		for (int r = 0; r <= h; ++r) {
			map[r][0] = map[r][w + 1] = '#';
		}
		for (int c = 0; c <= w; ++c) {
			map[0][c] = map[h + 1][c] = '#';
		}

		// input
		int whiteCount = 0;
		string S;
		for (int r = 1; r <= h; ++r) {
			cin >> S;
			for (int c = 1; c <= w; ++c) {
				map[r][c] = S[c-1];
				if (map[r][c] == '.') ++whiteCount;
			}
		}

		// 흰 칸의 개수가 3의 배수가 아니면 모두 덮을 수 없다
		if (whiteCount % 3 != 0) {
			cout << 0 << endl;
		}
		else {
			cout << putBlock(1,1) << endl;
		}

	}
	return 0;
}