[AOJ][C++] 게임판 덮기 - BOARDCOVER

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

algospot.com :: BOARDCOVER

종만북 두번째 문제 게임판 덮기이다.

 

어려서 엄마손잡고 교보문고에 갔을 때 이런 비슷한 이런 장난감을 홍보하는걸 봤던 기억이 난다.

 

그 때 장난감 체험을 했었는데 공간지각력이 오진다고 직원이 엄청 치켜세워줬었다. 

 

그때는 정말 내가 공간지각력이 뛰어난줄 알았는데 커서 보니깐 그냥 카카오맵 보고 집 찾아갈 수 있는 정도인 것 같다ㅋㅋㅋ

 

종만북 풀이를 보기 전에 혼자 풀어보는 시간을 가졌다.

 

문제 접근 과정은 다음과 같았다.

 

1.게임판 크기가 20*20이 최대이고 테스트 케이스가 적으니깐 완탐으로 풀 수 있을 것 같다.(사실 그냥 완탐파트라서 완탐으로..)

2.모든 경우를 다 탐색 해야하니깐 모든 칸에 대해서 모든 퍼즐을 넣을 수 있는 모양을 전부 넣어보면 되겠다.

3.퍼즐을 돌리면 4가지 모양이 나오는구나 4가지 모양에 대해서 완탐을 재귀로 구현하면 되겠구만!

 

여기까지 생각하고 구현을 하고 종만북을 봤는데 역시 종만북은 오늘도 나에게 가르침을 주었다,,,

 

"3의 배수로 나눠지지 않는다면 해결할 수 없다"

 
그래서 처음부터 3으로 나눠지지 않는 경우를 제외하는 코드를 추가했다.

그리고 책에 왼쪽 위부터 순서대로 탐색하기로 한다는 내용이 있었다.

뭔가 너무 당연하게 그렇게 구현했었는데 정해진 순서로 세는 것이 중복으로 세는 경우를 제할 수 있는 방법이라는 것을 새삼스레 상기하게 되었다.

 

그렇게 구현을하고 테스트를 돌렸는데 뭐가 틀렸는지 계속 답이 나오지 않았다.

 

분명 방법론도 맞고 설계도 틀리지 않은 것 같은데 대체 틀리는 이유가 뭘까 싶었다.

 

2시간 걸린 끝에 알게 된 틀린 이유는 4가지 모양의 블럭을 넣어보는 과정에서 

 

   ㅁ

ㅁㅁ

 

모양의 블럭을 넣을 때  

 

＠ㅁ

ㅁㅁ

 

＠모양을 기준으로 ＠을 탐색할 때 빈칸이면 블럭을 넣어보는 방식으로 코드를 짰는데

＠위치가 벽이더라도 ㅁ세칸 위치가 빈공간이라면 위와 같은 모양의 블럭을 넣을 수 있는 상태일 것인데 @위치가 벽이기 때문에 블럭을 넣지 않고 다음 줄로 넘어간 것이다.

이걸 수정하니 AC가 나왔다.

 

아직 종만북의 간결한 풀이를 따라가기엔 멀었다.

#include <iostream>
#include <cstdio>
using namespace std;
char map[100][100];
int H, W, answer=0, dot=0;
int dy[4][3]={{0,0,1},{0,0,1},{0,1,1},{1,0,1}}, dx[4][3]={{0,1,0},{0,1,1},{0,0,1},{0,1,1}};

bool in_range(int y, int x)
{
    if((x>=0) && (y>=0) && (y<H) && (x<W))
        return true;
    else
        return false;
}

void solve(int y, int x, int dnum)
{
    if(dnum==dot) // 기저상태 : 모든 빈칸을 덮었을 경우
    {
        answer++;
        return;
    }

    if(in_range(y, x))
    {
        for(int i=0;i<4;i++)
        {
            if(map[y+dy[i][0]][x+dx[i][0]]=='.' && map[y+dy[i][1]][x+dx[i][1]]=='.' && map[y+dy[i][2]][x+dx[i][2]]=='.')
            {
                for(int j=0;j<3;j++)
                {
                    map[y+dy[i][j]][x+dx[i][j]]='#';
                }

                if((x+1==W) && in_range(y+1,x))
                {
                    solve(y+1,0,dnum+3);
                }
                else if(in_range(y,x+1))
                {
                    solve(y,x+1,dnum+3);
                }

                for(int j=0;j<3;j++)
                {
                    map[y+dy[i][j]][x+dx[i][j]]='.';
                }
            }
        }
        if(map[y][x]=='#' && (x+1==W) && in_range(y+1,x))
        {
            solve(y+1,0,dnum);
        }
        else if(map[y][x]=='#' && in_range(y,x+1))
        {
            solve(y,x+1,dnum);
        }
    }
}

int main()
{
    char str[100];
    int C;
    scanf("%d",&C);

    while(C--)
    {
        dot=0;
        answer=0;
        for(int i=0;i<100;i++)
        {
            str[i]=NULL;
            for(int j=0;j<100;j++)
            {
                map[i][j]='#';
            }
        }
        scanf("%d %d",&H,&W);
        for(int i=0;i<H;i++)
        {
            scanf("%s",str);
            for(int j=0;j<W;j++)
            {
                map[i][j]=str[j];
                if(str[j]=='.')
                    dot++;
            }
        }

        if(dot%3!=0) // 3의 배수로 나눠지지 않는다면 해결할 수 없다.
        {
            printf("0\n");
            continue;
        }

        solve(0,0,0);

        printf("%d\n",answer);
    }
    

    return 0;
}