6.5 게임판 덮기(ID : BOARDCOVER)

6.5 게임판 덮기(ID : BOARDCOVER)

제출일 : 2021-01-05

문제 풀이 시간 : 1H

---

Link : 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 을 넘지 않습니다.

출력

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

예제

입력

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

출력

0
2
1514

문제 풀이 접근

가능한 경우의 수를 재귀함수를 이용하여 구현하였습니다.

예전 N-QUEEN 문제를 풀어봐서 그런지 쉽게 풀수 있었습니다.

왼쪽 위가 0,0이 되도록 하여 블록의 4가지 방향의 상대위치 값을 미리 저장하고. 배열에서 빈 공간을 만났을때 4가지 블록을 비교하여 해당 칸에 블록을 둘 수 있는경우 재귀함수를 호출하도록 문제를 해결하였습니다.

각 메소드명을 기준으로 간단하게 설명을 하면

• Solve()는 재귀의 메인이 되는 메소드입니다.

• check(k,i,j)는 현재 위치(i,j)가 빈칸.일 경우에 호출되는 함수로 k번째 블록이 들어갈 수 있는지 확인하는 메소드입니다.

• isRange(nr,nc)는 (nr, nc)의 값이 보드를 벗어나는지 확인하는 메소드입니다.

• set(k, i, j, v)는 (i, j)를 기준으로 K번째 블록의 위치 값을 v로 변경하는 메소드입니다. 이 함수를 통해 백트래킹을 쉽게 구현할 수 있습니다.

코드

언어 : JAVA

실행 시간 : 180ms

import java.util.Scanner;

public class Main {
    static int H, W, ans;
    static int[][] map;
    static int[][][] block = { { { 0, 0 }, { 0, 1 }, { 1, 1 } }, { { 0, 0 }, { 0, 1 }, { 1, 0 } },
                              { { 0, 0 }, { 1, 0 }, { 1, 1 } }, { { 0, 0 }, { 1, 0 }, { 1, -1 } }, };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int C = sc.nextInt();
        for (int tc = 0; tc < C; tc++) {
            H = sc.nextInt();
            W = sc.nextInt();

            map = new int[H][W];
            int cnt = 0;
            for (int i = 0; i < H; i++) {
                String input = sc.next();
                for (int j = 0; j < W; j++) {
                    map[i][j] = input.charAt(j) == '.' ? 0 : 1;
                    if (map[i][j] == 0)
                        cnt++;
                }
            }

            if (cnt % 3 != 0) {
                System.out.println(0);
            } else {
                ans = 0;
                solve(cnt);
                System.out.println(ans);
            }
        }
    }

    private static void solve(int cnt) {
        if (cnt == 0) {
            ans++;
            return;
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (map[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        if (check(k, i, j)) {
                            set(k, i, j, 1);
                            solve(cnt - 3);
                            set(k, i, j, 0);
                        }
                    }
                    return;
                }
            }
        }

    }

    private static void set(int k, int r, int c, int v) {
        for (int i = 0; i < 3; i++) {
            int nr = r + block[k][i][0];
            int nc = c + block[k][i][1];
            map[nr][nc] = v;
        }
    }

    private static boolean check(int k, int r, int c) {
        for (int i = 0; i < 3; i++) {
            int nr = r + block[k][i][0];
            int nc = c + block[k][i][1];
            if (!isRange(nr, nc) || map[nr][nc] == 1) {
                return false;
            }
        }
        return true;
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < H && 0 <= nc && nc < W)
            return true;
        return false;
    }
}