- 문제
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
답안코드
#include<iostream>
#include<string>
// Algospot - BOARDCOVER
using namespace std;
int T, H, W;
int wayCount;
int board[20][20];
int coverType[4][3][2] = { // cover함수에서 발견된 최좌측최상단 흰색 칸을 기준으로
{ { 0, 0 }, { 1, 0 }, { 0, 1 } }, // 중복 처리 흐름에 거역하지 않는, 가능한
{ { 0, 0 }, { 0, 1 }, { 1, 1 } }, // L자 배치 형태가 바로 이 네 가지이다.
{ { 0, 0 }, { 1, 0 }, { 1, 1 } }, // 한 행을 먼저 훑고, 그 다음 행을 훑는 식으로
{ { 0, 0 }, { 1, 0 }, { 1, -1 } } // 중복 처리 흐름이 이어지므로, 이 네 가지만
}; // 가능함. 이것의 발견이 매우 주요한 idea
bool isInRange(int y, int x) { // ny와 nx가 범위 벗어나는지 체크
return 0 <= x && x < W && 0 <= y && y < H;
}
bool set(int y, int x, int type, int block) {
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 (!isInRange(ny, nx)) // L자 칸이 모두 배치 가능한 경우만 다룬다
check = false;
else if ((board[ny][nx] += block) > 1) // 이미 cover된 곳이거나, 검은 칸과
check = false; // 겹치는 경우도 빼준다.
}
return check; // 상단의 체크를 모두 통과한 경우만 cover한다.
}
void cover(void) {
int x = -1, y = -1; // default 세팅 : 발견 못함 구분을 위해 -1로 둔 것
for (int i = 0; i < H; i++) { // 중복 처리를 위해 좌측 상단에서부터
for (int j = 0; j < W; j++) { // 훑으면서, 처음으로 발견되는 uncover
if (board[i][j] == 0) { // 칸을 특정해 x와 y에 지정한다.
x = j;
y = i;
break;
}
}
if (y != -1) break; // 최초 발견 위치를 기록하므로 나머진 필요x
}
if (y == -1) { // 모두 cover되어 흰색 칸이 발견되지 않으면
wayCount++; // 경우의 수가 하나 count되는 것이다.
return;
}
for (int i = 0; i < 4; i++) {// 해당 흰색 칸에서 4가지 경우의 L자 배치 가능 여부 체크
if (set(y, x, i, 1)) // cover를 씌우면 board배열 값이 0->1이 된다.
cover();
set(y, x, i, -1); // 그리고 재귀적 흐름에 의해 다시 벗겨낸다.
}
}
int main(void) {
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> H >> W;
wayCount = 0;
int dotCount = 0;
for (int i = 0; i < H; i++) {
string str; // 행 string으로 받는 것이 보다 더 깔끔하다.
cin >> str;
for (int j = 0; j < W; j++) { // 열 번호를 기준으로 처리해주면 된다.
if (str[j] == '#')
board[i][j] = 1;
else
board[i][j] = 0;
}
}
if (dotCount % 3 != 0) {
cout << 0 << '\n';
continue;
}
cover();
cout << wayCount << '\n';
}
}첫 시도에서 실패한 이유는, 너무 DFS적인 관점으로 함수를 작성하려 했다는 점이다. 이 문제 풀이에서 가장 주요한 부분은 바로, 위의 cover 함수에서 '남아있는 흰색칸 중 최좌측, 최상단의 칸'을 특정해주는 부분이다.
DFS적인 관점에서 처음 코드를 짤 때, 바로 이 부분에 대한 고민이 많았고, 결국 제대로 해결하지 못하게 되는 원인이 됐다. H x W의 중첩 반복문을 돌리되, 첫 번째 흰색칸을 찾으면 멈추도록 설계하는 이 쉬운 것을 제대로 해내지 못했다.
이 최초의 흰색칸이 발견되지 않는 상황이 바로 재귀의 탈출조건이다.
그 다음, 이 부분의 처리도 매우 주요했다. 흰색칸을 기점으로, 4가지의 'L자 배치 가능 경우'를 모두 체크해, 배치하고 cover 함수를 재귀호출하는 것이다. 그러면 재귀호출 흐름에 의해 모든 경우에 대한 State Space Tree가 형성된다.
for (int i = 0; i < 4; i++) {
if (set(y, x, i, 1))
cover();
set(y, x, i, -1);
}if문을 통해 배치 가능한 경우에만 재귀호출을 진행하고, 해당 재귀흐름이 끊겨서 돌아올 때는 다시 set함수에 -1을 인자로 보냄으로써 배치를 풀어주는 것이다. set 함수 내의 else if 조건문 체크 과정에서 배치 상태가 풀리게 된다.
한편,
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 } }
}; 이러한 표현방식도 상당히 주목할만하다. 4가지 배치 가능 경우에 대해, 3개의 칸의 상대 위치를 xy좌표로 표현한 것이다. 이때, 가능한 4가지 배치 경우는, 중복 처리를 목적으로 한 행을 훑고 그 다음 행을 훑는 스캔 방식을 거역하지 않는 선에서 배치가 가능한 4가지의 경우를 말한다.
ㅂㅁ ㅂㅂ ㅂㅂ ㅁㅂㅁ
ㅂㅂ ㅂㅁ ㅁㅂ ㅂㅂㅁ
의 가지가 경우가 있다. (ㅂ이 L자를 구성하는 칸)
