[종만북] BOARDCOVER - 게임판 덮기 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-BOARDCOVER

 

 

풀이

  모든 칸에 블록을 놓아본다고 하자. 이 경우 흰 칸의 수는 50을 넘지 않는다고 했고, 블록 하나에 3칸씩이므로 최대 16개를 덮으면 된다. 블록의 모양은 4가지이므로, O(C x 4^16) 이 필요하다. 방법을 좀 다르게 생각해서 각 칸마다 놓거나 안놓거나 해봐도 O(C x 2^50)이므로 마찬가지로 불가능하다.

 

  여기서 생각해볼 점은, 블록의 3칸 중 가장 상단 좌측의 위치를 기준으로 놓는다고 생각해보자.

 

  그리고 주어진 게임판의 상단부터 하단으로, 좌측에서 우측으로 쭉 보면서 블록을 놓는다고 해보자. 이렇게 되면 만약 블록을 놓지 않고 그냥 지나쳤을 때, 해당 위치엔 다시는 블록을 놓을 수 없음이 증명된다. 예를들어 3x3 게임판에 첫번째 칸을 선택하지 않고, 2번째 칸부터 놓는다고 할 때 위의 규칙대로라면 첫 번째 칸은 이후 다시는 채울 방법 자체가 없다. 따라서 차례대로 보면서 빈칸이라면 무조건 4개의 모양 중 하나를 선택해야 한다.

 

  이 경우 빈 칸이 생기더라도 L자 모양으로 3칸이 주변에 없다면 거기서 루프가 종료되므로, 시간복잡도를 수학적으로 계산하긴 힘들지만 모양이 안맞는 경우들이 생각보다 많아서 생각보다 횟수가 크게 늘어나지 않는다. 예를들어 최악의 경우라 생각되는 아래의 경우 몇 번 재귀 함수가 호출되는지 확인해봤다.

1
6 8
........
........
........
........
........
........

위의 경우 coverBoard 함수는 68,656 번밖에 호출되지 않았다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int DR[][] = {{1, 1, 0, 0}, {1, 1, 1, 1}};
    private static final int DC[][] = {{0, 0, 1, 1}, {-1, 1, 1, 0}};
    private boolean[][] arr = new boolean[22][22];
    int r, c;


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        int c = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (c-->0) {
            sb.append(main.solution()).append('\n');
        }
        System.out.print(sb);
    }

    private int solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        int remain = setupBoard();
        if (!isRemainModBy3(remain)) {
            return 0;
        }
        return coverBoard(remain / 3, 0);
    }

    private int setupBoard() throws IOException {
        int remain = 0;
        for (int i = 0; i < arr.length; i++) {
            Arrays.fill(arr[i], true);
        }
        for (int i = 1; i <= r; i++) {
            String s = br.readLine();
            for (int j = 1; j <= c; j++) {
                arr[i][j] = s.charAt(j-1) == '#' ? true : false;
                if (!arr[i][j])
                    remain++;
            }
        }
        return remain;
    }

    private boolean isRemainModBy3(int remain) {
        return remain%3 == 0;
    }

    private int coverBoard(int remain, int sr) {
        if (remain == 0) {
            return 1;
        }

        for (int i = sr; i <= r; i++) {
            for (int j = 0; j <= c; j++) {
                if (arr[i][j]) continue;

                int cnt = 0;
                for (int dir = 0; dir < 4; dir++) {
                    int nr1 = i+ DR[0][dir];
                    int nc1 = j+ DC[0][dir];
                    int nr2 = i+ DR[1][dir];
                    int nc2 = j+ DC[1][dir];
                    if (arr[nr1][nc1]||arr[nr2][nc2]) continue;

                    arr[nr1][nc1] = true;
                    arr[nr2][nc2] = true;
                    arr[i][j] = true;
                    cnt += coverBoard(remain-1, i);
                    arr[nr1][nc1] = false;
                    arr[nr2][nc2] = false;
                    arr[i][j] = false;
                }
                return cnt;

            }
        }
        return 0;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.