[Algospot] BOARDCOVER (탐색)

#. 문제 

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

* 이 문제의 저작권은 Algospot에 있습니다.

H*W 크기의 게임판이 있습니다. 

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

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

[ 입력 ]

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

[ 출력 ]

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

#. 문제 해결 과정

  1. 문제를 읽고 이해하기

  2. 문제를 익숙한 용어로 재정의 + 추상화

    - 게임판의 흰 칸을 모두 3칸짜리 L자 모양의 블록으로 덮어야 함

    - 블록들을 자유롭게 회전 가능하지만, 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가면 안됨

    - 게임판이 주어지면 이를 덮는 방법의 수를 계산하여 출력

    - 조건

      ㄴ 테스트 케이스의 수 C (C <= 30)

      ㄴ 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20)

      ㄴ 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않음

  3. 어떻게 해결할지 계획 세우기(알고리즘, 자료구조 선택) -> 풀이

  4. 계획 검증하기(수행 시간과 사용 메모리 확인)

    - 수행 시간 : 2초 이내 / 사용 메모리 : 64MB 이하

    - 'ㄱ'자 한 블록을 놓을 때마다 네 가지의 선택지, 최대 50/3(16)개의 블록을 놓기 때문에 가능한 답의 상한은 4^16 => 2^32

  5. 계획 수행하기

  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아보기

#. 풀이

  1. 테스트 케이스의 수 C (C <= 30) 입력

  2. 2개의 정수 H, W (1 <= H,W <= 20) 입력

  3. 배열에 게임판의 블록들을 저장

    - 흰 칸이 50을 초과하면 에러

    - 흰 칸이 3의 배수가 아닌 경우 게임판을 덮을 수 없으므로 0 return (기저 사례)

  4. 게임판의 빈 칸을 찾아 set() 함수에 넘겨주는 cover() 함수

    - 중복의 경우를 제외하기 위해 각 단계마다 빈 킨의 가장 윗, 가장 왼쪽 칸을 먼저 덮도록 실행 (기준)

    - 첫 번째 빈 칸을 찾은 후 'ㄱ'자 블록을 덮을 방법을 하나하나 시도 -> set() 함수로 재귀 호출

    - 'ㄱ'자 블록이 놓였다면 남은 게임판을 재귀 호출에 넘겨 경우의 수를 계산

  5. 블록을 높는 set() 함수

    - 블록이 놓였다면 true 반환

    - 블록이 겹치거나, 검은 칸을 덮거나, 게임판을 나가는 경우 false 반환

#. 코드

import java.io.*;
import java.util.StringTokenizer;
 
public class C66_BOARDCOVER {
    // 'ㄱ'자 블록을 놓을 수 있는 상대적 위치
    public static int[][][] blockType = {
            {{0,0}, {0,1}, {1,0}},
            {{0,0}, {0,1}, {1,1}},
            {{0,0}, {1,0}, {1,1}},
            {{0,0}, {1,0}, {1,-1}},
    };
    public static int[][] board;
    public static int C, H, W;
    
    public static boolean set(int y, int x, int type, int act) {
        boolean check = true;
        // 'ㄱ'자 블록을 board에 놓아보기
        for(int i=0; i<3; i++) {
            int dy = y + blockType[type][i][0];
            int dx = x + blockType[type][i][1];
            if(dy<0 || dy>=H || dx<0 || dx>=W)    // 블록이 게임판으로 나갈 경우
                check = false;
            else if((board[dy][dx] += act) > 1) // 블록이 겹치는 경우 & 블록 치우기
                check = false;
        }
        return check;
    }
    
    /* 4. board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환하는 함수 */
    public static int cover() {
        // 채우지 못 한 가장 위&왼쪽 에 있는 칸 탐색
        int y = -1, x = -1;
        for(int hg=0; hg<H; hg++) {
            for(int wd=0; wd<W; wd++) {
                if(board[hg][wd] == 0) {
                    y = hg;
                    x = wd;
                    break;
                }
            }
            // 빈 칸을 찾았을 경우 반복문에서 탈출
            if(y != -1) break;    
        }
        // 모든 칸을 채웠을 경우 1 반환
        if(y == -1) return 1;
        
        int ret = 0;
        // 가장 위&왼쪽에 있는 빈 칸에 'ㄱ'블록을 덮을 4가지 방법을 시도
        for(int type=0; type<4; type++) {
            // board[y][x]를 해당 type으로 덮을 수 있다면 재귀 호출
            if(set(y, x, type, 1))
                ret += cover();
            // 덮을 수 없다면 덮었던 블록을 치우기
            set(y, x, type, -1);
        }
        return ret;
    }
    
    public static void Boardcover() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        /* 1. 테스트 케이스 입력 */
        C = Integer.parseInt(br.readLine().trim());
        assert C <= 30 : "Error :: C(testCase) <= 30";
        
        for(int tc=0; tc<C; tc++) {
            /* 2. H(Height)과 W(Width) 입력 */
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            H = Integer.parseInt(st.nextToken());  // Height
            W = Integer.parseInt(st.nextToken());  // Width
            assert 1 <= H || 1 <= W || H <= 20 || W <=20 : "Error :: 1 <= H,W <= 20";
 
            /* 3. board에 블럭을 저장 */
            board = new int[H][W];
            
            int countWhiteBlock = 0;
            for(int hg=0; hg<H; hg++) {
                String tempString = br.readLine();
                for(int wd=0; wd<W; wd++) {
                    // 잘못된 블럭이 입력될 경우 예외 처리
                    assert tempString.charAt(wd)=='#' || tempString.charAt(wd)=='.' : 
                        "Error :: block is available only int # or .";
                    if (tempString.charAt(wd)=='#') 
                        board[hg][wd] = 1;
                    else
                        countWhiteBlock++;
                }
            }
            
            // 데이터가 잘 들어갔는지 출력해서 확인
//            for(int hg=0; hg<H; hg++) {
//                for(int wd=0; wd<W; wd++) {
//                    bw.write(String.format("%d",board[hg][wd]));
//                }
//                bw.write("\n");
//            }
//            bw.write("\n");
 
            assert countWhiteBlock <= 50 : // 흰 칸이 50칸을 초과하면 에러 발생
                "Error :: countWhiteBlock <= 50";
            // 흰 칸이 3의 배수가 아닐 경우 0 출력 
            if(countWhiteBlock%3 != 0)
                bw.write(String.format("%d\n", 0));
            // 모든 칸이 이미 다 채워져있는 경우
            else if(countWhiteBlock == 0)
                bw.write(String.format("%d\n", 1));
            else
                bw.write(String.format("%d\n", cover()));
        }
        bw.close();
    }
    
    public static void main(String[] args) throws IOException {
        C66_BOARDCOVER.Boardcover();
    }
}
 

#. 결과

  - Input --------------------------------------------------------

3 

3 7 

#.....# 

#.....# 

##...## 

3 7 

#.....# 

#.....# 

##..### 

8 10 

########## 

#........# 

#........# 

#........# 

#........# 

#........# 

#........# 

########## 

------------------------------------------------------------------

  - Output --------------------------------------------------------

0

2

1514

------------------------------------------------------------------