[BOARDCOVER] 게임판 덮기

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

예제 입력

3  3 7  #.....#  #.....#  ##...##  3 7  #.....#  #.....#  ##..###  8 10  ##########  #........#  #........#  #........#  #........#  #........#  #........#  ##########

예제 출력

0 2 1514

---

문제 풀이

완전 탐색을 이용해 해결하자. 흰 칸의 수가 3의 배수가 아닌 경우를 따로 처리 해야 됨.

주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮으면 된다.

1. 한 칸을 덮는 4가지 방법 - coverType

2. 보드판 - board

/* L 블록을 이용해서 게임판을 덮는 방법의 수 */
/* 2019-07-08 게임판 덮기 */

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

const int coverType[4][3][2] = {
	{ { 0,0 },{ 1,0 },{ 0,1 } },
	{ { 0,0 },{ 0,1 },{ 1,1 } },
	{ { 0,0 },{ 1,0 },{ 1,1 } },
	{ { 0,0 },{ 1,0 },{ 1,-1 } }
};

//이 칸을 덮을 수 있는지 판단하고 board판을 덮거나 덮었던 블록을 없앤다
bool set(vector<vector<int> >&board, int y, int x, int type, int delta) {
	bool check = true;

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

		//보드판 범위를 넘어가는지
		if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) {
			check = false;
		}
		else if ((board[ny][nx] += delta) > 1) check = false; // 덮인 칸을 또 덮는 경우 false
	}
	return check;
}

int cover(vector<vector<int> >&board) {
	int y = -1, x = -1;
	for (int i = 0; i < board.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			if (board[i][j] == 0) { // 가장 먼저 덮을 칸 찾기
				y = i;
				x = j;
				break;
			}
		}
		if (y != -1) break; // for문 한번더 멈추기
	}

	if (y == -1) return 1;
	int ret = 0;

	for (int i = 0; i < 4; i++) {
		if (set(board, y, x, i, 1)) ret += cover(board);
		set(board, y, x, i, -1);
	}

	return ret;
}
int main() {
	int c, h, w;
	cin >> c; //test case

	for (int i = 0; i < c; i++) {
		char temp;
		int white = 0;
		cin >> h >> w;
		vector<vector<int> > board(h, vector<int>(w, 0));

		//보드판 그리기
		for (int k = 0; k < h; k++) {
			for (int j = 0; j < w; j++) {
				cin >> temp;
				if (temp == '#') board[k][j] = 1; // 덮히지 않은 칸은 1로 저장
				else white++;
			}
		}

		if (white % 3 != 0) cout << 0;
		else cout << cover(board)<<endl;

	}
}

 

알고리즘 문제해결 전략 1의 코드를 이용해서 풀었다. 어제 풀었던 소풍과 비슷한 문제라는 생각이 들었지만 보드판 내에서 상대 위치를 이용하는 방법에 익숙지 않아 책의 도움을 빌렸다.

먼저 흰 칸의 수가 3의 배수가 아닐 경우에는 무조건 답이 없으니 그 부분을 따로 처리했다. 이 외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수 n을 얻은 뒤, 문제의 답을 생성하는 과정을 n조각으로 나눠 한 조각에서 한 블록을 내려놓게 하면 된다. 즉 재귀 함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸 들을 재귀 호출을 이용해 덮도록 하면 된다.

---

 

coverType[4][3][2] 는 블록을 구성하는 세 칸의 상대적 위치의 목록이다. 

{ { 0,0 },{ 1,0 },{ 0,1 } }, // Γ { { 0,0 },{ 0,1 },{ 1,1 } }, // ㄱ { { 0,0 },{ 1,0 },{ 1,1 } }, // ㄴ { { 0,0 },{ 1,0 },{ 1,-1 } } // ┘

[4]는 각 4개의 타입, [3]은 각 타입을 구성하는 칸의 위치, [2]는 한 칸의 상대 좌표를 의미한다.

set 함수는 이 칸에 블록을 놓을 수 있는지 판단하고, 놓을 수 있다면 블록을 놓는 역할도 한다. 그뿐 아니라 블록을 제거하는 역할도 수행할 수 있다.

bool set(vector<vector >&board, int y, int x, int type, int delta)

board - 보드판, y,x - 내려놓을 위치, type - 4가지 타입 중에서 어떻게 내려놓을 건지, delta - 내려놓을 건지, 제거할 건지

set 함수에선 type이 정해져서 들어오기 때문에 그 type에 맞는 상대 위치의 3가지 블록을 넣을 수 있는지 아닌지 판단하고 넣으면 된다.

이때 첫번째 if문이 충족된다면 else if문은 건들지 않기 때문에 board [ny][nx]의 값이 바뀌지 않는다.

하지만 보드판 범위를 넘어가지 않는다면 delta에 따라 행동해야 한다. else if문에서는 board [ny][nx] += delta를 먼저 수행하는데, 이때 나올 수 있는 경우의 수는 다음과 같다

1. delta==1 (블록을 놓는 경우) : 1 + 0(board) -> 1 / 1 + 1(board) -> 2
2. dalta==-1 (블록을 제거하는 경우) : -1 + 0(board) -> -1 / -1 + 1(board) -> 0

else if 문을 만족해서 check가 false가 되는 경우는 블록이 있는 곳에 또 놓는 경우인 '2' 밖에 없다.

이 경우엔 board[ny][nx]의board [ny][nx]의 값이 2가 되고 check는 false로 return 되는데 cover 함수에서 if문을 만족시키지 않기 때문에 바로 set(board, y, x, type, -1)이 수행되어 다시 이전의 board [ny][nx]의 값이 1이 됨으로 신경 쓰지 않아도 된다.

cover 함수에서는 가장 먼저 덮을 칸을 찾는다. 이때 중복 문제를 해결하기 위해 가장 위에 있고 왼쪽에 있는 칸을 우선적으로 찾는다. 이때 덮을 칸이 없다면 모든 칸을 덮은 경우의 수 하나를 찾았다는 뜻임으로 return 1을 해준다.

그 뒤 4번 도는 for문을 이용해서 4가지 type 모두를 test한다. 이때 set 함수를 이용해서 블록을 놓을 수 있는지 아닌지 판단하고 블록을 배치한다. 배치 한 다음에는 다른 경우의 수를 찾기 위해서 블록 배치를 취소한다. 

 

전체적으로 다 풀고 나니 소풍과 비슷한 형태의 문제였다. 하지만 아직 재귀 호출과 완전 탐색을 구현 하는데 어려움을 겪어 힘들었다. 또한 노트북이 좋지 않아 완전 탐색으로 구현하면 오래 기다려야 해서 기다림이 귀찮았당..