[Week 2] BOARDCOVER self review - Yunhyunjo

[Yunhyunjo]

1. 해결 시도 과정

가능한 L블록을 다 넣어가며 반복하면 될거라고 생각했다.

2. 아이디어

나올 수 있는 L자 블록을 만들어 놓고 왼쪽 상단 부터 흰 칸을 찾아 거기서 들어갈 수 있는 L자 블록을 모두 대입해 본뒤 맞는다면 블록을 채운 뒤 재귀호출을 통해 다음 흰 칸에 대해 반복 수행한다.

3. 코드 설명

#include <iostream>
#include <string>

using namespace std;

int map[20][20]; // board
int white; // 흰칸
int w, h; // 검은 칸
int cnt; // 방법의 수
void start();
int findL();
int startxy[2]; // 흰 칸이 처음 시작되는 위치
int arr[4][4] = { { 0,1,1,1 },{ 1,0,1,-1 },{ 1,0,1,1 },{ 0,1,1,0 } };  // L자 블록의 경우의 수

int main(void) {
	int c;
	cin >> c;
	while (c--)
	{
		cin >> h >> w;
		string str;
		cnt = 0;
		white = 0;
		for (int i = 0; i < h; i++) {
			cin >> str;
			for (int j = 0; j < w; j++) {  // board 세팅 및 흰 칸 수 세기
				if (str[j] == '#') {
					map[i][j] = 1;
				}
				else {
					map[i][j] = 0;
					white++;
				}
			}
		}
		if (white % 3 == 0) {
			cnt = findL();
		}
		cout << cnt << "\n";
	}
}

void start() {  // 흰 칸의 위치를 찾는 함수
	bool x = false;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (!map[i][j]) {
				startxy[0] = i;
				startxy[1] = j;
				x = true;
				break;
			}
		}
		if (x) break;
	}
}
int findL() {  // L자 블록으로 채울 수 있는지 찾는 함수
	start();  // 흰 칸의 위치를 찾는 함수
	int i = startxy[0];
	int j = startxy[1];
	for (int k = 0; k < 4; k++) {
		if (i + arr[k][0] >= 0 && j + arr[k][1] >= 0 && i + arr[k][2] >= 0 && j + arr[k][3] >= 0) {  // 보드의 영역을 벗어나지 않도록
			if (!map[i + arr[k][0]][j + arr[k][1]] && !map[i + arr[k][2]][j + arr[k][3]]) {  // L자 블록을 채울 수 있을 때
				map[i + arr[k][0]][j + arr[k][1]] = 1;
				map[i + arr[k][2]][j + arr[k][3]] = 1;
				map[i][j] = 1;							// L자 블록을 채운다
				white -= 3;  // 남은 흰 칸의 갯수 
				if (white > 0) {         // 아직 채울 칸이 남았다면
					findL();  // 재귀 호출을 통해 반복
					map[i + arr[k][0]][j + arr[k][1]] = 0;
					map[i + arr[k][2]][j + arr[k][3]] = 0;
					map[i][j] = 0;                            // 다른 방법도 찾기 위해 방금 채운 L자 블록을 초기화 한다.
					white += 3;
				}
				else {          // 다 채웠다면
					map[i + arr[k][0]][j + arr[k][1]] = 0;
					map[i + arr[k][2]][j + arr[k][3]] = 0;
					map[i][j] = 0;                          // 다른 방법도 찾기 위해 방금 채운 L자 블록을 초기화 한다.
					white += 3;
					return cnt += 1; // 다 채웠으니 cnt를 +1해준다.
				}
			}
		}
	}
	return cnt;
}

L자 블록이 맞는다면 블록을 채우고 다음 흰 칸에 대해서는 재귀 호출을 통해 반복해주었다.

4. 막힌 점 및 개선 사항

문제에 나온 예제들은 답이 잘 나오는데 오답이 뜨는걸 보면 다른 예제를 넣으면 안되는 듯 싶다. 재귀호출하는 쪽에서 문제가 있는것 같은데 다시 한 번 생각해 봐야할 듯 싶다.