[Algorithm] 백준/17136 :: 색종이 붙이기

* 핵심 개념

삼성 4월 역량테스트에 나왔던 문제다.

Backtracking으로 구현하면 되지만, 최적화를 하지 않으면 시간이 무지오래걸린다.

우선, 구현 순서에 대해 알아보면

1. 10*10 맵을 돌면서 1인지 확인한다.
2. 1이 있다면 5*5 색종이를 덮을 수 있는지 확인한다.
3. 색종이를 덮을 수 있다면 해당 맵을 0으로 바꾼다.
4. 색종이를 덮을 수 없다면 더 작은 색종이를 확인한다.

이런 방식으로 진행되는 Backtracking 방식이다.

하지만, 단순하게 조건만 따라 구현하면 시간 초과가 날 수밖에 없다.

이를 위해 다음과 같은 방법을 사용한다.

1. 매개변수로 row 값을 넘겨준다. 맵을 탐색할 때 row부터 시작하면 이전 줄은 확인하지 않아도 되므로 연산을 줄일 수 있다.    >> int r 파라미터로 사용
2. 입력 시에 1의 총 개수를 구하고 파라미터에 색종이로 지운 1의 개수를 계산하면서 넘긴다.        >> int total 파라미터로 사용
• 만약 지운 1의 개수와 입력받은 1의 개수가 같다면 ans에 최소값을 저장하고 return한다.
3. 큰 색종이부터 들어갈 수 있는지 확인해 보기 때문에, 큰 색종이로 덮을 수 있다면 작은 색종이는 확인해볼 필요 없이 가능하다. >> boolean flag 이용
• 1*1 색종이까지 확인했는데도 색종이를 넣을 수 없다면 함수를 return한다.
4. 해당 좌표를 바꾼 후에 아직도 1이 남아있으면 유효하지 않은 경우이므로 return한다.        >> 가지치기

가지치기 때문에 정말 고생이 많았던 문제다.

코드가 깔끔하지는 않지만 누군가에게 도움이 되길 바라며 공유한다.

* 문제

문제

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

<그림 1>

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

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

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] paper = {0, 5, 5, 5, 5, 5};
    public static int[][] map = new int[10][10];
    public static int ans = Integer.MAX_VALUE, one_cnt = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 10; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                one_cnt += map[i][j];       //1의 개수 세기
            }
        }
        //r = 해당 row, cnt = 사용한 색종이수, total = 제거한 1의 개수
        Backtracking(0, 0, 0);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
 
    public static void Backtracking(int r, int cnt, int total) {
        if (ans <= cnt) return;      //현재 값보다 색종이를 많이쓰면 가지치기
        if (total == one_cnt) {      //1을 다 채운 경우
            ans = Math.min(ans, cnt);
            return;
        }
        for (int i = r; i < 10; i++) {     //r부터 시작
            for (int j = 0; j < 10; j++) {
                if (map[i][j] == 1) {
                    boolean flag = false;  //큰 색종이로 덮을 수 있으면 이후 색종이는 확인해 보지 않아도 된다
                    for (int k = 5; k >= 1; k--) {
                        if ((i + k) <= 10 && (j + k) <= 10 && paper[k] > 0) {
                            if (!flag) {
                                flag = check(i, j, k); //k*k 색종이를 덮을 수 있으면 check = true
                            }
                            if (flag) {
                                setVisited(i, j, k);
                                paper[k]--;
                                Backtracking(i, cnt + 1, total + k * k);
                                paper[k]++;
                                setVisited(i, j, k);
                            }
                        }
                    }
                    if (!flag) return;          //색종이를 못덮는 경우
                }
                if (map[i][j] == 1) return;     //덮고나서도 해당좌표를 못지우는경우
            }
        }
    }
 
    //size만큼의 색종이를 사용할 수 있는지 확인
    public static boolean check(int r, int c, int size) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (map[i][j] == 0) return false;
            }
        }
        return true;
    }
 
    //방문한 점을 XOR 연산
    public static void setVisited(int r, int c, int size) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                map[i][j] = map[i][j] ^ 1;
            }
        }
    }
}