[ALGOSPOT] 게임판 덮기(BOARDCOVER)

[ALGOSPOT] 게임판 덮기(BOARDCOVER)

게임판 덮기

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOARDCOVER
  • 2000ms
  • 65536kb
  • 5720
  • 2631 (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

노트

import java.util.Scanner;
 
public class Main {
    // int[블록을 놓는 모양][모양에 따른 블록들의 상대좌표][상대 좌표]
    // 가장 왼쪽 위 블록을 기준으로 상대좌표를 산정한다.
    private static int[][][] coverType = { 
            { { 0, 0 }, { 1, 0 }, { 0, 1 } }, // ┌
            { { 0, 0 }, { 0, 1 }, { 1, 1 } }, // ┐
            { { 0, 0 }, { 1, 0 }, { 1, 1 } }, // └
            { { 0, 0 }, { 1, 0 }, { 1, -1 } } // ┘
    };
 
    // 블록을 쌓을 수 있는지 확인해주는 메소드
    // Stack이 1이면 쌓고, Stack이 -1이면 뺀다.
    private static boolean set(int[][] board, int y, int x, int type, int stack) {
        boolean ok = true;
 
        for (int i = 0; i < 3; i++) {
            int ny = y + coverType[type][i][0];
            int nx = x + coverType[type][i][1];
 
            // 보드 밖으로 나갔을 때, false 반환
            if (ny < 0 || ny >= board.length || nx < 0 || nx >= board[0].length) {
                ok = false;
            // 검은 칸에 쌓았을 때(Stack = 2) false 반환
            } else if ((board[ny][nx] += stack) > 1) {
                ok = false;
            }
        }
        return ok;
    }
 
    // 보드에 블록을 쌓는 메소드
    private static int cover(int[][] board) {
        int y = -1, x = -1;
 
        // 보드의 왼쪽 위에서부터 빈칸을 찾는 로직
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {
                    y = i;
                    x = j;
                    break;
                }
            }
            // 빈칸을 찾아 가로줄 for문을 빠져 나왔을 때, 다음 세로줄로 넘어가면 안되므로 다시 break
            if (y != -1) {
                break;
            }
        }
 
        // 모든 빈칸이 메꿔지면 y,x의 값은 -1이므로 이 때, 하나의 경우를 만족하므로 1 반환.
        if (y == -1) {
            return 1;
        }
 
        int result = 0;
 
        for (int type = 0; type < 4; type++) {
            // board[y][x]를 type형태로 덮을 수 있으면 재귀 호출로 다음 블록을 놓는다.
            if (set(board, y, x, type, 1)) {
                result += cover(board);
            }
            // 보드에 쌓았던 블록을 치운다.
            set(board, y, x, type, -1);
        }
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int loop = sc.nextInt();
        int[] result = new int[loop];
 
        while (loop-- > 0) {
            int height = sc.nextInt();
            int width = sc.nextInt();
            int[][] board = new int[height][width]; // board[i][j]의 값이 1 이상이면 블록이 존재 0이면 없는것.
 
            String tmp;
            sc.nextLine(); // Scanner 에서 \n을 제거하기 위함.
 
            for (int i = 0; i < height; i++) {
                tmp = sc.nextLine().replace("#", "1").replace(".", "0");
                for (int j = 0; j < width; j++) {
                    board[i][j] = Integer.parseInt(tmp.substring(j, j + 1));
                }
            }
 
            result[loop] = cover(board);
        }
 
        for (int i = result.length - 1; i >= 0; i--) {
            System.out.println(result[i]);
        }
    }
}