[종만북] 06 .6 게임판 덮기

https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

문제

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

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

입력

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

출력

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

 

 

 

완전탐색을 이용하여 입력한 게임판에 정해진 모양의 블록으로 덮는 경우의 수를 출력하는 문제이다.

재귀를 이용해 모든 경우의 수를 따져주는 완전탐색 기법을 사용하는데

중복을 피하기 위해 특정한 순서를 강제했다. 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 방법을 사용한다.

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 도형의 회전을 고려한 4가지 유형
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}}
};

//게임판의 x,y 위치에서
//delta가 1이면 게임판을 type번 도형 모습으로 덮는다
//delta가 -1이면 게임판의 type번 도형을 없앤다
bool set(vector<vector<int>>& board, int y, int x, int type, int delta){
    bool ok = true;
    for(int i=0;i<3;i++){
        //x,y를 기준으로 type번째 도형의 모습
        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())
            ok = false;
        //delta가 -1인 경우
        else if((board[ny][nx] += delta) > 1)
            ok = false;
    }
    return ok;
}

int cover(vector<vector<int>>& board){
    int y = -1;
    int 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){
        //board(y,x)를 type번 도형으로 덮을 수 있으면 재귀 호출
        if(set(board,y,x,type,1))
            ret += cover(board);
        //덮었던 블록을 치운다
        set(board,y,x,type,-1);
    }
    return ret;
}

int main(){
    int test_case;
    cin >> test_case;

    int y,x;
    while(test_case--){
        cin >> y >> x;
        vector<vector<int>> board(y,vector<int>(x,0));
        string tmp;

        for(int i=0;i<y;i++){
            cin >> tmp;
            for(int j=0;j<tmp.size();j++){
                if(tmp[j] == '#')
                    board[i][j] = 1;
            }
        }

        cout << cover(board) << endl;

    }
}

코드는 종만북에 있는 코드 그대로입니다