[Java] 알고스팟 : BOARDCOVER

문제 링크

1.

완전탐색(브루트포스) 문제

 

2.

자세한 풀이는 책 참고 (p.161)

 

• 블록 한 개를 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하기
• 빈칸 중 좌상단을 기준으로 블록을 두기 (즉, 기준점 위와 왼쪽은 검은 칸)
• 그렇게 되면 기준 점에서 블록을 놓을 수 있는 경우의 수는 4가지

 

3.

 import java.util.Scanner;

public class BOARDCOVER {
    static int height, weight, wall;
    static int dir[][][] = { { { 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 void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();

        for (int i = 0; i < c; i++) {
            height = sc.nextInt();
            weight = sc.nextInt();
            wall = 0;
            int[][] board = new int[height][weight];

            for (int j = 0; j < height; j++) {
                String input = sc.next();
                for (int k = 0; k < weight; k++) {
                    char temp = input.charAt(k);
                    if (temp == '#') {
                        board[j][k] = 1;
                        wall += 1;
                    }
                }
            }
            // 빈칸의 개수가 3의 배수가 아니면 불가능
            if ((height * weight - wall) % 3 != 0) {
                System.out.println("0");
            } else {
                System.out.println(solve(board));
            }
        }

        sc.close();
    }

    static int solve(int[][] board) {
        int y = -1, x = -1;
        int ret = 0;

        // 비어있는 칸 찾기
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < weight; j++) {
                if (board[i][j] == 0) {
                    y = i;
                    x = j;
                    break;
                }
            }
            // 찾았을 경우 반복문 종료
            if (y != -1)
                break;
        }

        // 모든 칸을 다 채운 경우
        if (y == -1) {
            return 1;
        }

        for (int type = 0; type < 4; type++) {
            if (check(board, y, x, type, 1)) {
                ret += solve(board);
            }
            check(board, y, x, type, -1);
        }

        return ret;
    }

    static boolean check(int[][] board, int y, int x, int type, int delta) {
        boolean flag = true;

        for (int i = 0; i < 3; i++) {
            int ny = y + dir[type][i][0];
            int nx = x + dir[type][i][1];

            if (ny < 0 || ny >= height || nx < 0 || nx >= weight) {
                flag = false;
            } else if ((board[ny][nx] += delta) > 1) {
                flag = false;
            }
        }
        return flag;
    }
}

 

 

4.

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만)