[완전 탐색] BOARDCOVER

[1. 문제 재정의 및 추상화]

1. H*W 크기의 게임판에서 모든 흰 칸을 세칸짜리 L 자 모양의 블록으로 덮어야 함.
2. 이 형태의 블록은 회전해서 놓을 수 있지만, 서로 겹치거나, 검은색 칸을 덮거나, 게임판 밖으로 나가서는 안됨.
3. '#' 은 검은 칸, '.' 은 흰 칸을 의미함
4. H,W 는 최소 1 에서 최대 20 이며, 흰 칸의 수는 50을 넘지 않는다.
5. 흰 칸을 덮는 경우의 개수를 계산해야 함.

 

[2. 해결 계획]

1. 가능한 경우의 수 이므로 완전 탐색 방식을 사용해 본다.
2. 흰 칸의 개수가 3의 배수가 아니면 어떤 방식으로도 흰 칸을 모두 덮을 수 없다.
   => L 자 모양은 세칸 짜리 이다.
3. 블록을 놓는 순서는 중요하지 않다.
   => (A):└, (B): ┘가 있을 때 (A) 를 먼저 놓고, (B) 를 놓나 / (B) 를 놓고 (A) 를 놓는 것은 같은 경우이다.
4. 블록을 놓는 순서를 강제하도록 한다.
   => 좌상단에 먼저 블록을 회전 시켜가면서 배치하고, 그 다음은 재귀로 반복한다.
   => Base Case: 더 이상 블록을 놓을 수 없는 경우
5. 좌상단에 블록을 먼저 배치 할 때 놓을 수 있는 방식은 아래 4가지와 같음
   

   

6. 각 경우에서 * 를 기준으로 X, Y 에 대한 상대좌표를 구할 수 있음

 

[3. 계획 검증]

1. 한 블록마다 최대 4가지의 선택이 있으며, 입력에서 흰 칸의 최대 개수는 50이므로, 최대 floor(50/3) = 16 개의 블록마다 4 개의 경우가 발생하므로, 4^16 = 2^32 이지만 블록을 놓은 방식이 정해지면, 그 다음 블록이 정해지는 경우는 한정되게 된다.
   => 아래와 같은 경우에서 * 를 기준으로 흰 블록의 모양이 결정되면, 다음 위치에 놓일 블록은 한개로 고정 될 수 밖에 없다.
   => 이런식으로 답의 상한은 2^32 보다 더 작다고 볼 수 있다. (직관?)
   

   

 

[4. 구현]

#include <iostream>
#include <cstring>

char board[20+1][20+1];

// 좌상단에서 우하단으로 내려가는 구조이므로
// 기준점을 잡는 방식이 중요함.
// 현재 발견한 지점은 최소 위와 왼쪽은 검은 색이므로
// 블록을 놓을 수 있는 방법이 정해져 있음.
const int coverTypes[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}}
};

bool canCover(const int H, const int W, 
              const int y, const int x, const int type)
{
    for (int count = 0; count < 3; count++)
    {
        const int dy = y + coverTypes[type][count][0];
        const int dx = x + coverTypes[type][count][1];
        // 배열의 범위를 벗어나는 경우
        if (dy < 0 || dy >= H || dx < 0 || dx >= W)
        {
            return false;
        }
        // 검은 칸과 겹치는 경우,
        else if (board[dy][dx] == '#')
        {
            return false;
        }
        // 블록이 놓인 위치는 검은 칸으로 변경되어 있으므로
        // 흰칸에는 아무 것도 놓여있지 않아서
        // 블록을 위치 하게 할 수 있다.
    }
    return true;
}

// 배열을 순회하는 방식이 canCover() 와 같으므로
// 코드 재사용이 가능하도록 변경 할 수 있다.
void setCover(const int y, const int x, const int type, const char value)
{
    for (int count = 0; count < 3; count++)
    {
        const int dy = y + coverTypes[type][count][0];
        const int dx = x + coverTypes[type][count][1];

        board[dy][dx] = value;
    }
}

int cover(const int H, const int W)
{
    // find white space
    int y = -1; int x = -1;
    for (int h = 0; h < H; h++)
    {
        for (int w = 0; w < W; w++)
        {
            if (board[h][w] == '.')
            {
                y = h;
                x = w;
                break;
            }
        }
        if (y >= 0) break;
    }
    // BaseCase: 흰 공간이 없으므로 모두 채운 경우
    if (y == -1 || x == -1)
    {
        return 1;
    }
    
    int ret = 0;
    for (int type = 0; type < 4; type++)
    {
        // 현재 위치에서 블록을 놓을 수 있다면
        if (canCover(H, W, y, x, type))
        {
            // 블록을 놓고
            setCover(y, x, type, '#');
            // 다음 경우에 대해서 확인 함
            ret += cover(H, W);
            // 이후 블록을 다시 놓기 위해 흰 칸으로 변경
            setCover(y, x, type, '.');
        }
    }

    return ret;
}


int main()
{
    int TC;
    int H, W;

    scanf("%d", &TC);
    for (int c = 0; c < TC; c++)
    {
        scanf("%d %d", &H, &W);
        memset(board, 0, sizeof(board));

        for (int d = 0; d < H; d++)
        {
            scanf("%s", board[d]);
        }
        // 흰칸의 개수를 먼저 체크 해 볼 수 있다.
        printf("%d\n", cover(H, W));
    }
}