[완전탐색] 게임판 덮기(문제 ID:BOARDCOVER, 난이도:하)

1. 문제정의

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

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

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

---

2. 문제 설계

완전 탐색을 이용해 모든 경우의 수를 알아보는 것입니다. 재귀 호출을 이용해 코드를 만들어 봅시다.

부분 문제 정의
항상 빈 칸 중에서 가장 위, 그 중에서도 가장 왼쪽에 칸을 처음으로 채운다고 가정합니다. 채우는 방법은 4가지 유형입니다. 각 부분문제가 성공적으로 채워질때마다 +1이 될 것이고 결과적으로 경우의 수를 모두 더한 수가 됩니다.

---

3. 구현

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

//타일 선택 : 가장 위쪽 그리고 왼쪽이 기준
//덮는 방법 : 4가지 x 3칸 x (y, x)
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의 (y, x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다
//delta가 1이면 덮고, -1이면 덮었던 블록을 없앤다
//게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때 false 반환
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 >= (int)board.size() || nx < 0 
    || nx >= (int)board[0].size()) //범위를 초과할 경우
                       ok = false;
               else if ((board[ny][nx] += delta) > 1) //겹쳐질 경우
                       ok = false;
        }
        return ok;
}

//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환
//board[i][j]=1 이미 덮인 칸 혹은 검은 칸
//board[i][j]=0 아직 덮이지 않은 칸
int cover(vector<vector<int>> &board){
        //아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다
        int y = -1, x = -1;
        for (int i = 0; i < (int)board.size(); i++){
               for (int j = 0; j < (int)board[i].size(); j++)
                       if (board[i][j] == 0) {//아직 채우진 못한 칸 찾음
                              y = i;
                              x = j;
                              break;
                       }
               if (y != -1) break;
        }

        //기저 사례: 모든 칸을 채웠으면 1을 반환
        if (y == -1) return 1;

        int ret = 0;
        for (int type = 0; type < 4; type++){
               //만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출
               if (set(board, y, x, type, 1))
                    ret += cover(board);
               //덮었던 블록 치운다
               set(board, y, x, type, -1);
        }
        return ret;
}

int main(void){
        int testCase, H, W;
        char bw[20]; 

        cin >> testCase;
        for (int i = 0; i < testCase; i++){
               cin >> H >> W;
    vector<vector<int> > board(H, vector<int>(W, 0));
               for (int i = 0; i < H; i++) {
                       cin >> bw;
                       for (int j = 0; j < W; j++)
                               board[i][j] = (bw[j] == '#') ? 1 : 0;
               }
               cout <<"OUTPUT : "<<cover(board) << endl;
        }
        return 0;
}

---

4. 테스트

 

 

출처 :  https://algospot.com/judge/problem/read/BOARDCOVER