[백준] 17136. 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

예제 입력 5 

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 5

7

---

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

public class Main {
    static int[][] arr;
    static final int n = 10;
    static int ans;
    static int[] quantity = {0, 5, 5, 5, 5, 5};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[n][n];

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        ans = 99999;
        color(0);
        System.out.println(ans == 99999 ? -1 : ans);
    }

    public static void color(int count) {
        int sR = -1, sC = -1;
        Loop1:
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                if(arr[i][j] == 1) {
                    sR = i;
                    sC = j;
                    break Loop1;
                }
            }
        }

        if(sR == -1 && sC == -1) {
            ans = Math.min(ans, count);
            return;
        }

        int max = 5;

        while(max > 0) {
            boolean isOK = true;
            // max 크기로 색종이 붙일수 있는지
            Loop2:
            for(int i = 0; i < max; i++) {
                for(int j = 0; j < max; j++) {
                    if(sR + i >= 10 || sC + j >= 10 || arr[sR + i][sC + j] == 0) {
                        isOK = false;
                        break Loop2;
                    }
                }
            }
            if(isOK) {
                break;
            }
            max--;
        }

        for(int i = 1; i <= max; i++) {
            if(quantity[i] == 0) {
                continue;
            }

            for(int r = sR; r < sR + i; r++) {
                for(int c = sC; c < sC + i; c++) {
                    arr[r][c] = 0;
                }
            }
            quantity[i]--;
            color(count + 1);
            for(int r = sR; r < sR + i; r++) {
                for(int c = sC; c < sC + i; c++) {
                    arr[r][c] = 1;
                }
            }
            quantity[i]++;
        }
    }
}

백트래킹 문제이다.

 

10 x 10칸의 격자를 탐색하면서 1인 부분에 종이를 붙여야 하니 맨 처음 오는 1의 인덱스를 기억한다.

 

해당 칸의 위치를 찾으면 종이의 크기가 최대(5칸)인것부터 최소(1칸)인것까지 어떤게 들어갈 수 있는지 찾는다.

 

해당 인덱스에 max값(종이 크기)를 더해 10을 넘기지 않고 0이 없으면(종이를 붙일 수 있는 공간이 있다.) 종이를 붙였다 가정하고(0으로 세팅) 다음 1이 있는곳으로 넘어간다. 그리고 다시 0을 붙인곳을 다시 1로 복구한 다음 종이의 크기를 1칸씩 늘려 몇개의 종이가 들어갔는지 카운팅을 한 다음 인덱스가 -1, -1(전부 붙여 못 찾을 시) 재귀를 끝낸다.