[알고리즘 문제해결 전략]6장. 무식하게 풀기_④

BOARDCOVER in algospot

---

problem

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOARDCOVER
  • 2000ms
  • 65536kb
  • 6335
  • 2902 (45%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

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

입력

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

출력

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

예제 입력

3 
3 7 
#.....# 
#.....# 
##...## 
3 7 
#.....# 
#.....# 
##..### 
8 10 
########## 
#........# 
#........# 
#........# 
#........# 
#........# 
#........# 
########## 

예제 출력

0
2
1514

Thinking

 우리가 보드판에 놓을 수 있는 블록의 모양은 다음과 같다.

[그림 1] 퍼즐 유형

이를 주어진 보드판에 채워넣는 방법에 대하여 고민을 해보면, 아래와 같이 대입이 가능하다.

[그림 2] 보드 예시

 그러면 [그림 2]와 같이 각각의 보드를 제일 위의 왼쪽의 칸을 채우기위해 서로 다른 퍼즐을 맞춘다고 생각을 한다면, 서로 다른 배치의 퍼즐을 입력하는 것과 동일한 것이므로 반복해서 서로 다른 퍼즐을 놓는 경우의 수를 구하면 된다.

Important code

int board[board_size][board_size];
int covers[4][3][2] =
{
    {{0,0},{0,1},{1,0}},
    {{0,0},{0,1},{1,1}},
    {{0,0},{1,0},{1,1}},
    {{0,0},{1,-1},{1,0}}
};
 
int setting(int i_flag, int j_flag, int type,int flag) {//선택할 퍼즐의 모양을 나타내기 위해 type을 사용한다. 
    int tmp_i, tmp_j;                                    //그리고 퍼즐을 놓을지 아니면 제거할지 flag로 선택한다.
    int cover_flag = 0;
    for (int i = 0; i < 3; i++) {
        tmp_i = i_flag + covers[type][i][0];
        tmp_j = j_flag + covers[type][i][1];
        if (tmp_i >= 0 && tmp_i < H && tmp_j >= 0 && tmp_j < W) {
            if (flag == set) {
                if (board[tmp_i][tmp_j] == empty) cover_flag++;//모든 곳에 놓을 수 있으면 cover_flag = 3이 된다.
                else {
                    return 0;//퍼즐을 놓을 수 없으므로 0(false)를 반환한다. 
                }
            }
            else if (flag == del) {
                if (board[tmp_i][tmp_j] == covered) cover_flag++;//제거할 퍼즐이 있으면 cover_flag = 3이 된다.
                else {
                    return 0;//퍼즐을 제거할 수 없으므로 0(false)를 반환한다.
                }
            }
        }
        else {
            return 0;//퍼즐이 보드를 벗어나면 퍼즐을 놓거나 제거할 수 없다 false 반환
        }
    }
    if (cover_flag == 3) {//퍼즐을 놓거나 제거한다.
        for (int i = 0; i < 3; i++) {
            tmp_i = i_flag + covers[type][i][0];
            tmp_j = j_flag + covers[type][i][1];
            if (flag == set) {
                board[tmp_i][tmp_j] = covered;
            }
            else if (flag == del) {
                board[tmp_i][tmp_j] = empty;
            }
        }
    }
    return 1;
}
 
void cover_block() {
    int i_flag,j_flag;
    i_flag = j_flag = -1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (board[i][j] == empty) {//보드에서 제일 위,왼쪽에서 빈부분을 탐색한다.
                i_flag = i;
                j_flag = j;
                break;
            }
        }
        if (i_flag != -1) break;
    }
    if (i_flag == -1) {//빈곳이 없으면 다 채워 진것이므로 한개의 case가 완성된 것이다.
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (setting(i_flag, j_flag, i, set) == 1) {//퍼즐 ㅏ나를 놓을 수 있으면 퍼즐을 놓고
            cover_block();//다시 재귀함수로 퍼즐을 새로 셋팅된 보드에서 다시 퍼즐을 놓는 것을 시도한다.
            setting(i_flag, j_flag, i, del);// 다른 퍼즐을 놓기위해 놓았던 퍼즐을 제거한다.
        }
    }
}

여기서 시행시간을 좀 더 줄이는 팁은 우리가 놓을 수 있는 퍼즐은 3의 크기의 퍼즐이므로 빈곳이 3의 배수가 아닌경우 퍼즐을 채울 수 없으므로 미리 걸러 준다.

Solve

success

출처

---

문제:  algosport BOARDCOVER문제( 링크 )