06 - 게임판 덮기 BOARDCOVER

1. 흰 칸에 4가지 타입의 ㄴ모양 블럭을 둬서 꽉 채우는 경우의 수를 출력.

 

2. 현재 위치 기준으로 

fx[4][3] = { {0,0,1}, {0,0,1}, {0,1,1}, {0,1,1} };

fy[4][3] = { {0,1,1}, {0,1,0}, {0,0,1}, {1,0,1} };

에 블럭을 두도록 설계하자.

 

3.map[][]에 문자 입력받고, mark[][]에 블럭을 둔 곳을 표시하도록 함. (입력받을 때 검정색 부분도 마크하도록 함)

map의 제일 좌상단을 기준으로 x가 1증가하는 방향(x범위 초과 시 y 1증가, x = 0)으로 탐색 

 

int go(int cy, int cx) //게임판을 덮는 경우의 수를 출력하는 재귀함수

 

기저:

 - 모든 블럭이 마크됐으면 게임판이 덮어 진 것으로 return 1

 - cx==w-1이면 cy+=1, cx=0

 - cy==h-1이면 게임판을 덮는 경우가 없는 것으로 return 0

재귀:

 -type 0~3까지 둘 수 있으면 두고 backtracking

 -둘 수 있던지 없던지 블럭을 안두는 경우도 재귀에 포함

 

4. 구현

#include <iostream>
#include <algorithm>
using namespace std;

const int fx[4][3] = { {0,0,1}, {0,0,1}, {0,1,1}, {0,1,1} };
const int fy[4][3] = { {0,1,1}, {0,1,0}, {0,0,1}, {1,0,1} };

int h, w;
bool mark[21][21];
char map[21][21];

int go(int cy, int cx) {
	//채우는 것이 가능한 경우
	bool isValid = true;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (mark[i][j] == false) {
				isValid = false;
				break;
			}
			if (!isValid) break;
		}
	}
	if (isValid) return 1;
	
	if (cx == w - 1) return go(cy + 1, 0);
	if (cy == h - 1) return 0; //채우는 것이 불가능 한 경우
	
	int ret = 0;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		bool flag = false;	
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			if (map[iy][ix] == '#' || mark[iy][ix] == true) {
				flag = true;
				break;
			} //못두는 경우
		}
		if (flag) {
			cnt++;
			continue; //다음모양
		}
		//이 모양 둘 수 있는 경우
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			mark[iy][ix] = true;
		}
		ret += go(cy, cx + 1);
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			mark[iy][ix] = false;
		}
	}
	ret += go(cy, cx + 1);
	return ret;
}

int main() {

	cin >> h >> w;
	fill(&mark[0][0], &mark[21][21], false);
	int cnt = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#') mark[i][j] = true;
			if (map[i][j] == '.') cnt++;
		}
	}
	if (cnt % 3 != 0) { cout << 0; return 0; }

	cout << go(0, 0) << '\n';

}

5. 검증

작은 입력(6, 8 모든 공간 하얀색인 경우 동작함)에는 작동하지만 책의 마지막 case 시간초과.

재귀가 너무 많이 발생하는 문제가 있음. 블럭을 배치할 수 있어도 배치하지 않는 경우를 살피기 때문에 모든 상황에서 재귀가 생김.

내 아이디어대로 하면 블럭을 배치할 때 (cy,cx)에 블럭을 두지 않는 경우가 생김. 

->저자의 아이디어로 블럭을 배치할 땐 (cy,cx)에 반드시 블럭을 두게 됨. (블럭을 배치할 수 있지만 배치하지 않는 경우는 살필 필요가 없음.) 

 

.수정 코드

#include <iostream>
#include <algorithm>
using namespace std;

const int fx[4][3] = { {0,1,1}, {0,0,1}, {0,0,1}, {0,0,-1} }; //ㄱ ㄴ
const int fy[4][3] = { {0,0,1}, {0,1,1}, {0,1,0}, {0,1,1} };

int h, w;
bool mark[21][21];

int go() {
	//채울 칸 정하기.
	int cy = -1, cx = -1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (mark[i][j] == false) {
				cy = i, cx = j;
				break;
			}
		}
		if (cy != -1) break;
	}
	if (cy==-1) return 1;
	
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		bool flag = false;	
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			if (mark[iy][ix] == true || ix<0 || iy>=h || ix>=w) {
				flag = true;
				break;
			} //못두는 경우
		}

		if (flag) continue; //못두는 경우 다음 타입
		
		//이 모양 둘 수 있는 경우
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			mark[iy][ix] = true;
		}
		ret += go();
		for (int j = 0; j < 3; j++) {
			int iy = cy + fy[i][j], ix = cx + fx[i][j];
			mark[iy][ix] = false;
		}
	}
	return ret;
}

int main() {

	cin >> h >> w;
	int cnt = 0;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char temp;
			cin >> temp;
			if (temp == '#') mark[i][j] = true;
			if (temp == '.') {
				mark[i][j] = false; 
				cnt++;
			}
		}
	}
	if (cnt % 3 != 0) { cout << 0; return 0; }

	cout << go() << '\n';
}

 

.후기

 한 문제에 너무 시간을 쏟으면 안된다는 얘기가 있는데, 내 능력이 너무 모자라서 문제해결의 틀만 짜는데도 시간이 너무 오래걸린다... 난이도 '하' 문제에서 이렇게 힘들어하는데 이 책을 너무 일찍 꺼낸게 아닌가 싶다