게임판 덮기 - 완전 탐색

H x W 크기의 게임판이 있다. 게임판은 검은 칸과 흰 칸으로 구성된 격자다. 이 때, 흰 칸을 L자 모양의 블럭으로 빈 공간 없이 덮으려고 한다. 모두 덮을 수 있는 경우의 수를 구하시오.

 

문제에서 모든 경우의 수를 구하라고 했기 때문에 완전 탐색 해야한다.

완전 탐색을 구현하기 위해서는 문제를 먼저 조각 낸다.

1. 블럭을 흰 칸에 놓는다.
2. 더 이상 놓을 블럭이 없으면 1을 리턴한다.

최대한 단순하게 문제를 만들어 보았다. 위의 과정을 반복하면 모든 게임판을 덮을 수 있다.

 

기저사례

1. 더 이상 놓을 블럭이 없으면 1을 리턴한다.
2. 모든 공간을 다 덮었으면 1을 리턴한다.

 

알고리즘 설명

1. 사용자로부터 게임판의 크기와 정보를 입력 받는다.

2. 3으로 나눠떨어지지 않는다면 빈 공간을 모두 채울 수 없기 때문에 바로 종료

3. 블럭의 수를 구한 후 매 함수 호출 마다 1개의 블럭을 놓는 재귀함수 시작

4. 처음 시작 위치는 가장 위의 왼쪽의 좌표부터 시작한다.

   1. 이 좌표로 시작하게 되면 해당 좌표 왼쪽과 위쪽은 자동으로 막혀있게 된다.
   2. 그럼으로써 블럭의 방향이 4가지로 고정된다.

5. 각 블럭은 4가지 방식으로 배치 할 수 있다.

   1. ㄴ, ㄱ과 역방향 2가지

6. 4가지 방식 중 배치 할 수 있는 좌표가 있다면 배치하고 재귀함수 호출

7. 하위의 모든 경우의 수를 순회 후 다음 방향 검사

   1. 다음 방향 검사 전 배치한 블럭을 뺀다

8. 위의 기저사례를 만족하면 해당 재귀함수 종료

 

bool CheckRotation(int h, int w, int direction, vector<vector<bool>>& boards)
{
	int height = boards.size();	
	int width = boards[0].size();

	switch (direction)
	{
	case 0:
		if(h+1 >= height || w - 1 < 0)
			return false;

		if(!boards[h + 1][w] && !boards[h + 1][w - 1])
			return true;

		break;
	case 1:
		if (h + 1 >= height || w + 1 >= width)
			return false;

		if(!boards[h + 1][w] && !boards[h + 1][w + 1])
			return true;

		break;
	case 2:
		if (h + 1 >= height || w + 1 >= width)
			return false;

		if(!boards[h + 1][w] && !boards[h][w + 1])
			return true;
		break;
	case 3:
		if (h + 1 >= height || w + 1 >= width)
			return false;

		if (!boards[h + 1][w + 1] && !boards[h][w + 1])
			return true;

		break;
	}

	return false;
}

void PutBlock(int h, int w, int direction, vector<vector<bool>>& boards, bool value)
{
	boards[h][w] = value;

	switch (direction)
	{
	case 0:
		boards[h + 1][w] = value;
		boards[h + 1][w - 1] = value;
		break;
	case 1:
		boards[h + 1][w] = value;
		boards[h + 1][w + 1] = value;
		break;
	case 2:
		boards[h + 1][w] = value;
		boards[h][w + 1] = value;
		break;
	case 3:
		boards[h][w + 1] = value;
		boards[h + 1][w + 1] = value;
		break;
	}
}

int FillBlock(int h, int w, vector<vector<bool>>& boards, int block)
{
	if (block == 0)
	{
		return 1;
	}

	int start[2];
	fill(start, start+2, -1);

	for(int i = 0; i < h; ++i)
	{
		for(int j = 0; j < w; ++j)
		{
			if(!boards[i][j])
			{
				start[0] = i;
				start[1] = j;
				break;
			}
		}

		if(start[0] != -1)
			break;
	}

	if(start[0] == -1) return 1;

	int ret = 0;
	for(int i = 0; i < 4; ++i)
	{
		if(CheckRotation(start[0], start[1], i, boards))		
		{
			PutBlock(start[0], start[1], i, boards, true);
			ret += FillBlock(h, w, boards, block-1);
			PutBlock(start[0], start[1], i, boards, false);
		}
	}

	return ret;
}

int main()
{
	int h, w;
	scanf("%d %d", &h, &w);

	int spaceCount = 0;

	vector<vector<bool>> boards;
	string line;
	getline(cin, line);

	for(int i = 0; i < h; ++i)
	{
		vector<bool> rowBoard;
		getline(cin, line);

		for (auto c : line)
		{
			bool isBlock = false;
			if (c == '#')
				isBlock = true;
			else
				++spaceCount;

			rowBoard.push_back(isBlock);
		}

		boards.push_back(rowBoard);
	}

	int block = spaceCount / 3;

	if(spaceCount % 3 != 0)
		return 0;

	cout << FillBlock(h, w, boards, block) << endl;
	
	return 0;
}

 

완전 탐색 문제는 항상 케이스 마다 1개씩 고정을 한다고 생각하면 풀기 쉽다. 모든 경우의 수를 구해야 하기 때문에 1개의 케이스를 고정 시키고 고정된 케이스를 제외한 나머지 중 1개를 뽑아서 고정 시키고, 다음 나머지 중 1개를 뽑아서 고정, ... 이런식으로 0이 될 때까지 반복하는 작업이다.

 

예전에는 완전 탐색을 위해서 반복문을 중복해서 순회하는 방식으로 했는데 그렇게 하면 알고리즘이 더 복잡해져서 오히려 구현하기가 더 어렵다. 재귀 함수를 이용하면 동작이 단순해지고 작성해야 할 코드의 양도 더 줄어든다.

 

완전 탐색 문제는 재귀적으로 해결하도록 생각하라