[종만북 문제] 게임판 덮기 (문제 ID : BOARDCOVER, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 완전탐색으로 블록을 덮어보자. 잘.

---

[종만북 문제] 게임판 덮기 (문제 ID : BOARDCOVER, 난이도 : 하)

일단, 해당 문제는 사실 블록을 어떻게 덮을지만 결정하면 대략적으로 풀이를 만들어 볼 수 있다. 

책에서는 위와 같이 덮는 방법 4개를 제시한다. 우리는 이 모델을 바탕으로 배열을 만들어 덮는 가짓수를 순회하도록 만들 것이다.

#include <iostream>
#include "stdlib.h"
#include <vector>

using namespace std;

int M, N;
int board[20][20];
int ans;
int blanks;

// 가능한 블록의 모양
int types[4][3][2] =
{ 
	{ {0, 0}, {0, 1}, {1, 0} },
	{ {0, 0}, {0, 1}, {1, 1} },
	{ {0, 0}, {1, -1}, {1, 0} },
	{ {0, 0}, {1, 0}, {1, 1} }
};

// delta 값에 따라 해당 블록을 덮을지 말지가 결정
// 1 이면 덮고, -1 이면 들어낸다. 두 번 덮었을 경우에도 어차피 들어낼 거라 상관없음
bool cover(int y, int x, int delta, int type)
{
	bool ok = true;

	for (int i = 0; i < 3; ++i)
	{
		int ny = y + types[type][i][0];
		int nx = x + types[type][i][1];

		if (ny < 0 || ny >= M || nx < 0 || nx >= N)
			ok = false;
		else if ((board[ny][nx] += delta) > 1)
			ok = false;
	}

	return ok;
}

void putCube()
{
	int y = -1;
	int x = -1;

	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (board[i][j] == 0)
			{
				y = i;
				x = j;
				break;
			}
		}
		if (y != -1)
			break;
	}

	// 모든 칸이 차 있으면 pass
	if (y == -1)
	{
		ans += 1;
		return;
	}

	for (int t = 0; t < 4; ++t)
	{
		// 덮을 수 있다면, 재귀호출
		if (cover(y, x, 1, t))
		{
			putCube();
		}
		// 덮었던 블록을 치운다
		cover(y, x, -1, t);
	}

}

void sol()
{
	ans = 0;

	// 빈 칸의 갯수가 3의 배수가 아니면 pass
	blanks = 0;
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
			if (board[i][j] == 0)
				blanks += 1;
	if (blanks > 0 && blanks % 3 == 0)
		putCube();

	cout << ans << endl;
}

void inputHandler()
{
	cin >> M;
	cin >> N;

	string line;
	for (int i = 0; i < M; ++i)
	{
		cin >> line;
		for (int j = 0; j < N; ++j)
		{
			if (line[j] == '.')
				board[i][j] = 0;
			else if (line[j] == '#')
				board[i][j] = 1;
		}
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

위의 코드를 실행하면, 통과를 하게 된다.

다만 완전 탐색이니까 시간 복잡도가 지수함수가 되지 않을까 하는 우려가 들 수는 있는데... 실제로 블록을 덮을 수 있는 가짓수가 그리 많지 않아, 그렇게까지 오래 걸리지는 않는다! 😎