[알고리즘] Algospot_BOARDCOVER

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

문제

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

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

입력

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

출력

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

정답코드

#include<bits/stdc++.h>
#define endl '\n'

int fdy[] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 1, 1};
int fdx[] = {0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 0 ,0};
int sdy[] = {-1, -1, 1, -1, 1, 1, -1, 1, 0, 0, 0, 0,};
int sdx[] = {1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1};

int t, h, w;

using namespace std;

int howMany(vector<vector<bool>>& c)
{
    int posH=-1, posW=-1;
    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            if(!c[i][j])
            {
                posH=i;
                posW=j;
                break;
            }
        }
        if(posH!=-1 && posW!=-1)    break;
    }

    if(posH==-1 && posW==-1)   return 1;

    int ret = 0;

    for(int i=0; i<12; i++)
    {
        if(posH+fdy[i] > -1 && posH+sdy[i]> -1 &&
           posH+fdy[i] < h && posH+sdy[i] < h &&
           posW+fdx[i] > -1 && posW+sdx[i]> -1 &&
           posW+fdx[i] < w && posW+sdx[i] < w)
        {
            if(!c[posH+fdy[i]][posW+fdx[i]] &&
               !c[posH+sdy[i]][posW+sdx[i]])
            {
                c[posH][posW]=c[posH+fdy[i]][posW+fdx[i]]
                =c[posH+sdy[i]][posW+sdx[i]]=true;

                ret+=howMany(c);

                c[posH][posW]=c[posH+fdy[i]][posW+fdx[i]]
                =c[posH+sdy[i]][posW+sdx[i]]=false;
            }
        }
    }

    return ret;
}


int main()
{
    cin >> t;

    while(t--)
    {
        cin >> h >> w;

        vector<string> v(h);
        vector<vector<bool>> c(h,vector<bool> (w,false));

        for(int i=0; i<h; i++)
            cin >> v[i];

        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(v[i][j]=='#')    c[i][j]=true;
            }
        }

        cout << howMany(c) << endl;
    }

    return 0;
}

풀이 및 사고과정

PICNIC문제에서 아이디어를 생각해냈다.
이번 문제를 보고 비슷하게 풀 수 있을 거 같아서 PICNIC문제에서 이해한 내용을 바탕으로 코드를 작성했다.

첫번째로 고민했던 부분은 빈 공간인 .을 만났을 때 해야하는 행동이었다.
.을 기준으로 총 12가지의 모양을 놓을 수 있었고 대입가능한 모든 모양을 재귀를 통해 하나씩 다 넣었다.
처음에는 모양을 8개로 착각해서 30분정도 헤맸다
더 간결하게 코드를 짤 수 있을 거 같았는데 괜히 내 머리가 복잡해질 거 같아서 12개의 좌표를 모두 배열에 넣어서 돌렸다.

두번째는 중복문제였는데 howmany함수에 들어갈 때마다 어차피 모양이 다 달라지기 때문에 신경쓰지 않아도 됐다.