백트래킹. 색종이 붙이기

문제

1x1, 2x2, 3x3, 4x4, 5x5 의 색종이가 5개씩 주어진다. 그리고 10x10 배열도 주어지고, 이 배열에서 1로 되어있는 부분을 주어진 색종이를 최소로 사용해서 덮을수있는 경우의 수를 구하는 문제이다.

해결방향성

일단 5x5 색종이부터 사용해야한다. 그리고 배열을 탐색하면서, 각각의 색종이가 5개보다 많이 사용되는 부분이 나오지않게, 처음부터 남은 색종이를 {0,5,5,5,5,5}로 선언해준다.(배열 인덱스를 편하기위해 1~5인덱스를 사용한다.) 그리고, 최소값 색종이보다 많이 사용되면 프루닝을 사용하고, 기본적으로 처음부터 배열을 훑으면서 1인원소를 발견하면, 모두 1인지를 체크하고, 배열 범위내인지 체크한다. 또한 사용할수있는 색종이가 남아있는지 카운트한다음, 백트래킹을 시도한다. 해당 부분은 이미 종이를 붙일수있는 것으로 확인되었으므로, 색종이를 붙이고(attach), paper[i]를 줄이고, dfs를 사용하여, 옆 열(column + 1)로 이동하고, cnt + 1 하며 다음 dfs를 사용한다. 처음 왼쪽위를 기준으로 하고, 계속 색종이를 붙이던중, 배열의 끝부분에 도달하면 cnt를 그만세고 min 비교후, 리턴한다. 또한, 1인 부분이 아닌경우에는 그냥 column을 1칸 이동시키며,

코드

package backTracking;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_17136 {
    static int answer;
    static int[][] board;
    static int[] paper = {0, 5, 5, 5, 5, 5};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 보드 채우기
        board = new int[10][10];
        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        answer = Integer.MAX_VALUE;

        dfs(0, 0, 0);


        if (answer == Integer.MAX_VALUE) {
            bw.write(String.valueOf(-1));
        } else{
            bw.write(String.valueOf(answer));
        }



        bw.flush();
        br.close();
        bw.close();
    }

    private static void dfs(int r, int c, int cnt) {
        if (r >= 9 && c > 9) { // 탈출조건 : (9,10)을 가면 -> (9,9)까지 다돌았으므로 cnt 값 대소비교 후 리턴
            answer = Math.min(answer, cnt);
            return;
        }

        if (answer <= cnt) { // 프루닝 : answer보다 cnt가 크면 탐색 x
            return;
        }

        if (c > 9) { // column 전부 봄 : 아래로 이동.
            // 이부분은 왜 dfs로 사용하는지 모르겠긴하네. -> 근데 옆열 이동할때마다 dfs 사용하는 걸로 보아,
            // 이 문제는 이동할때마다 dfs를 사용하는거같음. 기본적으로 색종이를 붙일때마다 깊이 우선 탐색을 하는 식이니 그런가.
            dfs(r + 1, 0, cnt);
            return;
        }

        if (board[r][c] == 1){ // 1이면 탐색
            for (int k = 5; k >= 1; k--) {
                // 카운트와 범위, 1 체크
                if (paper[k] > 0 && check(r,c,k)) // 백트래킹
                {
                    attach(r, c, k);
                    paper[k]--; // 횟수 줄임
                    dfs(r, c + 1, cnt + 1);
                    paper[k]++;
                    detach(r, c, k);
                }
            }
        } else{
            dfs(r, c + 1, cnt);
        }
    }


    private static boolean check(int r, int c, int k) {
        // kxk를 만족하는지 범위 체크
        for (int i = r; i < r + k; i++) {
            for (int j = c; j < c + k; j++) {
                if (i < 0 || i >= 10 || j < 0 || j >= 10) { // 범위에 속하지않으면
                    return false;
                }
                if (board[i][j] != 1) { // 1이 아니거나
                    return false;
                }
            }
        }
        return true;
    }

    private static void attach(int r, int c, int num) {
        for (int i = r; i < r + num; i++) {
            for (int j = c; j < c + num; j++) {
                if (board[i][j] == 1) { // 1 -> 0
                    board[i][j] = 0;
                }
            }
        }
    }
    private static void detach(int r, int c, int num) {
        for (int i = r; i < r + num; i++) {
            for (int j = c; j < c + num; j++) {
                if (board[i][j] == 0) { // 0 -> 1
                    board[i][j] = 1;
                }
            }
        }
    }
}

결론

느낀점은, column을 이동시킬때마다, row를 바꿀때마다 dfs를 사용한다는 점이다. 색종이를 붙일때마다 dfs를 사용해서 그런지, 한칸한칸 cnt만 늘리지않는 재귀로 들어가는 느낌. 색종이가 증가 할때마다 cnt + 1를 늘리는 깊이 우선 탐색을 하고, 또한, 프루닝을 통해 min보다 커지면 바로 return 시켜서 실행시간을 단축시킨점, 또한 되게 좋았다. 백트래킹의 최고봉 바로 아래 문제가 아닐까... 하여튼 이렇게 어려운 문제는 오랜만에 본다.