6.5문제: 게임판 덮기(ID: 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
First Thoughts
"H와 W의 범위가 제한적이다"
행과 열 최대 20개인 배열을 만들거나 동적할당으로 배열을 생성한다.
"L자 모양의 블록을 사용한다"
L자 모양의 블록은 총 3개의 흰색 칸을 덮는다. 그렇다면 흰색 칸의 총 개수가 3의 배수여야만 방법의 수를 구할 수 있다. 또한 L자 모양의 블록이 놓일 수 있는 방법(ㄱ자,ㄱ의 y축 대칭,ㄴ자,ㄴ의 y축 대칭)은 총 4가지가 있다. 이 4가지의 방법을 배열로 설정해놓는다.
"한 블록을 덮어놓고 그 이후에 또 다른 블록을 사용한다"
그 전에 사건이 이후에 사건에 영향을 미친다는 점과 똑같은 행동을 연속적으로 수행한다는 점에서 재귀함수를 사용해야겠다고 생각하였다. 또한 먼저 특정한 블록을 먼저 놓고 그 상태에서 또 다른 블록을 사용하는 것이 6.3소풍 문제랑 매우 비슷하다고 느꼈다.
My code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
char board[20][20];
int H, W;
int l[4][3] = { { 0,1,1 } ,{ 0,-1,1 } ,{ 0,-1,-1 } ,{ 0,1,-1 } };
bool check(char board[20][20]) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (board[i][j] == '.')
return false;
}
}
return true;
}
int fill(int block) {
int i, j,k;
int sum=0;
if (block==0&&check(board)) {
return 1;
}
for (i = 0; i < H; i++) {
for (j = 0; j < W; j++) {
if (board[i][j] == '.') {
for (k = 0; k < 4; k++) {
if (j+l[k][1]>0 && j+l[k][1]< W && i+l[k][2] >0 && i+l[k][2] <H &&board[i][j + l[k][1]] == '.' && board[i + l[k][2]][j] == '.') {
board[i][j] = board[i][j + l[k][1]] = board[i + l[k][2]][j] = 'l';
sum+=fill(block-1);
board[i][j] = board[i][j + l[k][1]] = board[i + l[k][2]][j] = '.';
}
}
}
}
}
return sum;
}
int main() {
int C;
int i;
int r, c;
int avail = 0;
int way = 0;
cin >> C;
for (i = 0; i < C; i++) {
avail = 0;
cin >> H >> W;
for (r = 0; r < H; r++) {
for (c = 0; c < W; c++) {
cin >> board[r][c];
if (board[r][c] == '.') {
avail += 1;
}
}
}
if (avail % 3 == 0) {
way=fill(avail / 3);
}
else {
way = 0;
}
cout << way << endl;
memset(board, 'X', sizeof(board));
}
}Answer code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int H, W;
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}} };
vector<vector<int>> board;
bool set(vector <vector<int>>& board, int y, int x, int type, int delta) {
bool ok = true;
for (int i = 0; i < 3; i++) {
const int ny = y + coverType[type][i][0];
const int nx = x + coverType[type][i][1];
if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
ok = false;
else if ((board[ny][nx] += delta) > 1)
ok = false;
}
return ok;
}
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;
}
}
if (y == -1) {
return 1;
}
int ret = 0;
for (int type = 0; type < 4; type++) {
if (set(board, y, x, type, 1)) {
ret += cover(board);
}
set(board, y, x, type, -1);
}
return ret;
}
int main(void) {
int C;
char a;
int way = 0;
int sum = 0;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> H >> W;
sum = 0;
for (int r = 0; r < H; r++) {
board.push_back(vector<int>(W));
for (int c = 0; c < W; c++) {
cin >> a;
if (a == '.') {
board[r][c] = 0;
sum += 1;
}
else if (a == '#') {
board[r][c] = 1;
}
}
}
if (sum % 3 == 0) {
way = cover(board);
}
else {
way = 0;
}
cout << way << endl;
board.clear();
}
}Differences & Faults
"L자 블록의 상대적 위치"
나는 L자 블록의 위치를 현재 흰색 칸이 있으면 그 흰칸이 항상 3꼭짓점 중 가운데 꼭짓점으로 생각하였다. 그래서 기준이 되는 흰색 칸이 L자 블록의 어떤 점일지도 모르는데 그렇게 설정을 하고 배열에 저장한 점이 잘못되었다. 또한 여태까지 3차원 배열을 사용해본 적이 없어 3차원 배열의 사용을 생각지 못하였다.
Impressions
"수치화된 게임보드"
게임판의 자료형을 무엇으로 하냐는 푸는 사람 자유이기도 하고 그에 따라 코드도 다르게 작성될 것이다. 하지만 정답 코드를 보면 L자 블록의 상대적 위치를 계산하기 위해 의도적으로 int형의 게임판을 사용한 거 같다.
"숫자의 의미"
앞서 말했듯이 게임판은 1(검정색 칸)과 0(흰색 칸)으로 이루어져있다. set함수를 보면 매개변수인 delta값에 따라 수행하는 역할이 다르다. delta값이 1일 때는 게임판에 1을 더해서 그 값이 1보다 크면 검정색 칸이거나 이미 채워진 칸임을 나타내고 -1일 때는 게임판에 -1을 더해서 원래 상태로 초기화해주는 역할을 한다.
Summary
분명 나 혼자 힘으로 생각하고 나의 생각을 코드로 구현하는 작업은 의미있는 작업인거 같다. 하지만 이 책의 정답 코드를 보면 힘이 빠진다. 너무나 논리적이고 간결하게 쓰여진 코드를 이해하가면서 느끼는 건 항상 '아직 많이 부족하구나'이다. 이번 문제의 아이디어는 뻔했지만 코드를 구현하는 방식에 있어서 많은 차이가 있었다. 또한 내가 자꾸 놓치는 한 가지들이 있는데 그 한 가지가 가장 핵심적인 거 같다. 아직 이 책의 공부방법을 체계적으로 잡지는 못했지만 빨리 방향을 정해서 이 책을 공부하는 과정 속에서 많이 성장하는 내가 되기를 바란다.
