알고리즘 문제ID BOARDCOVER C언어 풀이

알고리즘 풀이 세 번째 문제는 교재 알고리즘 문제해결전략 6.5장의 게임판 덮기(Board Cover)입니다.

문제 링크: 알고스팟 게임판 덮기

문제는 위 링크를 눌러 확인해주세요. 그럼 바로 풀이를 보도록 하겠습니다.

#include <stdio.h>
#pragma warning(disable:4996)

int C, c; // Test Cases
int H, W;
char pan[20][20];

// 문제: '.' 문자가 있는 공간을 3칸짜리 L자 블록으로 덮어라.
// 완료 조건: '.' 문자가 하나도 없다.
// 실패 조건: 3칸 미만 남았다. 남은 칸을 L자 블록으로 덮을 수 없다.
int func(void)
{
	// 최초의 '.' 문자 위치를 찾는다.
	int i_now = -1, j_now = -1, i, j, ret = 0;
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
			if (pan[i][j] == '.')
			{
				i_now = i; j_now = j;
				break;
			}
		if (i_now != -1) break;
	}
	if (i_now == -1) return 1; // Nothing left

	// x, y를 기준으로 L자를 만들 수 있는 모든 경우의 수에 대해 처리
	// x, y가 최초의 '.'이란 점을 고려하면 네 가지 방법 뿐
	if (i_now < H - 1 && j_now > 0 && pan[i_now + 1][j_now] == '.' && pan[i_now + 1][j_now - 1] == '.')
	{
		// # .
		// . .
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now + 1][j_now - 1] = '#';
		ret += func();
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now + 1][j_now - 1] = '.';
	}
	if (i_now < H - 1 && j_now < W - 1 && pan[i_now + 1][j_now] == '.' && pan[i_now + 1][j_now + 1] == '.')
	{
		// . #
		// . .
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now + 1][j_now + 1] = '#';
		ret += func();
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now + 1][j_now + 1] = '.';
	}
	if (i_now < H - 1 && j_now < W - 1 && pan[i_now + 1][j_now] == '.' && pan[i_now][j_now + 1] == '.')
	{
		// . .
		// . #
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now][j_now + 1] = '#';
		ret += func();
		pan[i_now][j_now] = pan[i_now + 1][j_now] = pan[i_now][j_now + 1] = '.';
	}
	if (i_now < H - 1 && j_now < W - 1 && pan[i_now][j_now + 1] == '.' && pan[i_now + 1][j_now + 1] == '.')
	{
		// . .
		// # .
		pan[i_now][j_now] = pan[i_now][j_now + 1] = pan[i_now + 1][j_now + 1] = '#';
		ret += func();
		pan[i_now][j_now] = pan[i_now][j_now + 1] = pan[i_now + 1][j_now + 1] = '.';
	}
	return ret;
}

int main(void)
{
	int i;
	scanf("%d", &C);
	for (c = 0; c < C; c++)
	{
		scanf("%d %d", &H, &W);
		for (i = 0; i < H; i++)
			scanf("%s", pan[i]);
		int ret = func();
		printf("%d\n", ret);
	}
	return 0;
}

풀이 코드가 깔끔하지 않아서 많이 부끄럽네요. 이 문제는 교재 6장의 취지에 맞게 '무식하게 풀기' 방식을 사용하여 풀이합니다. 문제를 세부 문제로 나누어 하나씩 해결해가는 재귀적인 방식을 택하고 있죠. 여기서의 문제는 '.' 문자가 있는 공간을 3칸짜리 L자 블록으로 덮어라, 입니다. 즉, L자 블록으로 하나 덮고 난 뒤, 나머지 공간에 대해서 다시 이 문제 풀이를 수행하면 되는 것이죠.

함수 func()가 그 역할을 담당합니다. func()에서는 좌상단에서부터 스캔하여 최초의 '.' 문자가 있는 위치를 찾고 난뒤, 이 위치를 기준으로 L자를 만들 수 있는 경우의 수에 대해 처리합니다. 지금 현재 위치 (i_now, j_now)가 '.'인 좌상단 최초의 좌표라는 걸 고려하면, 이 좌표를 포함하여 L자 블록을 덮을 수 있는 방법은 네 가지 방법 뿐입니다. (위 주석을 참고하세요.) 이들 각각의 경우에 수에 대해, 경계조건(각 좌표는 0 ~ H or W 사이여야 한다)을 확인하고, '.' 값인지 확인해서 L자 블록으로 덮을 수 있는 경우라면, 일단 덮고 (pan[...][...] = '#' 구문을 통해) func() 함수를 다시 호출하여 나머지 공간에 대해 덮을 수 있는 가지 수를 얻어냅니다. 그런 다음에는 다른 덮기 방식에 대해 확인해봐야 하므로, 기존에 덮었던 L자 블록을 들어내고(pan[...][...] = '.' 구문을 통해) 다음 if 문을 확인합니다.

func() 함수의 완료 조건은 '.' 문자가 하나도 없는, 즉 모든 공간이 L자 블록으로 덮인 상태입니다. 이 경우 1을 반환하여 개수가 제대로 취합되도록 합니다.

func() 함수의 실패 조건은 최초의 좌상단 '.'에 대해 남은 칸을 L자 블록으로 덮을 수 없는 경우입니다. 이 경우에는 4가지의 if 문이 참이 될 수 없으므로 ret == 0을 반환하여 탐색을 종료하게 됩니다.