[BOARDCOVER] 게임판 덮기

문제 주소

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

예제 입력

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

예제 출력

0
2
1514

깃허브 주소

https://github.com/SeungHwan-Choi/Algorithm/blob/master/src/bruteforce/BoardCover.java

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}} // ┘
    };

    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));
                } // end of for j
            } // end of for i

            result[loop] = cover(board);
        } // end of while

        for (int i = result.length - 1; i >= 0; i--) {
            System.out.println(result[i]);
        }
    }

    // 블록을 쌓을 수 있는지 확인해주는 메소드
    // 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;
            }
        } // end of for
        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;
                }
            } // end of for j
            // 빈칸을 찾아 가로줄 for문을 빠져 나왔을 때, 다음 세로줄로 넘어가면 안되므로 다시 break
            if (y != -1) {
                break;
            }
        } // end of for i

        // 모든 빈칸이 메꿔지면 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);
        } // end of for type
        return result;
    }
}

자바로 알고리즘 문제풀이를 준비하는 목적으로 '알고리즘 문제 해결 전략'을 분석하여 공부하고 있다. 추후 잊어버리지 않도록 정리한다.