백준 17136번: 색종이 붙이기 (Java)

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

 

 

 

 

 

 

 

---

 

풀이

안 되는 풀이: 그리디

왠지 '왼쪽 위에서 부터 시작하여, 큰 사각형이 가능한대로 붙이면 될 거 같다'라는 생각이 들기도 합니다.

반례)

		1	1	1	1	1	1	1
		1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1
	1	1	1	1	1	1	1	1

출력값: 8

정답: 3

-> 잘못된 배치를 했을 경우, 이를 무르는 방법이 있어야 할 거 같습니다.

 

 

올바른 풀이: 백트래킹

브루트포스는 시간복잡도 계산이 간단한 편이라 해도 되겠다는 판단이 상대적으로 쉬운 반면, 백트래킹은 재귀 구조상 안에서 얼마나 할 지 감이 안 잡혀서 풀이를 머뭇거리게 되는 측면이 있습니다. 본 문제도 크기가 10x10이라는 작은 크기로 정해졌으므로, 이런 사이즈에서는 모든 경우를 고려해보는 방법을 선택하는 용기(?)가 필요합니다.

(행, 열)을 (0, 0)에서 시작하여, 행이 10이 될 때까지 or 남은 1의 칸 수가 0이 될 때까지 for문을 돌면서 해당 위치에 크기가 1인 색종이를 붙일 수 있는지, 2인 색종이를 붙일 수 있는지, ... , 5인 색종이를 붙일 수 있는지 확인하여, 붙일 수 있으면 붙이고 다음 위치, 못 붙이면 그냥 다음 위치로 이동합니다. 팁으로는, 특정 위치에서 크기가 x인 색종이를 붙이지 못한다면, 크기가 x이상인 모든 색종이를 붙이지 못하므로 확인할 필요가 없습니다.

위 알고리즘은 '특정 위치에 색종이를 붙일 수 있는지'와 '특정 위치에 색종이를 붙이는 작업' 이 2가지가 대부분의 연산을 차지합니다. 최대 몇 번 수행할까요? 문제를 풀기 전에는 감이 안 잡혔지만, 구현하고 '예제 입력 6'(가장 많은 경우의 수가 나옵니다.)을 수행해보니, 대략 900만번의 단위 연산을 수행합니다. 즉, 충분합니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int ans = 100;
    static boolean[][] paper = new boolean[10][10];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total = 0;
        for (int i = 0; i < 10; i++ ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 10; j++) {
                if (Integer.parseInt(st.nextToken()) == 1) {
                    paper[i][j] = true;
                    total++;
                }
            }
        }
        backTracking(0, 0, 0, new int[] {0, 5, 5, 5, 5, 5}, total);
        System.out.println((ans == 100)? -1: ans);
    }
    
    // r == c == 0부터 시작하여, r == c == 9까지 탐색
    static void backTracking(int cnt, int r, int c, int[] papers, int left) {
        // 남은 1의 수가 0개이면 처리 완료
        if (left == 0) {
            ans = Math.min(ans, cnt);
            return;
        }
        // Note: 범위 벗어나는지 확인은 left == 0 체크 이후에 해야함.
        if (r >= 10) return;
        
        // 못 붙이는 위치라면 다음 자리로 넘어가기
        if (!paper[r][c]) {
            if (c < 9) backTracking(cnt, r, c+1, papers, left);
            else backTracking(cnt, r+1, 0, papers, left);
        }
        
        // l: 색종이 크기
        for (int l = 1; l <= 5; l++) {
            // 범위를 벗어나거나, 못 붙일 경우 -> 더 큰 색종이도 못 붙이니 바로 break
            if (r+l > 10 || c+l > 10 || !canPost(r, c, l)) break;
            if (papers[l] > 0) {
                post(r, c, l);
                papers[l]--;
                if (c < 9) backTracking(cnt+1, r, c+1, papers, left - l*l);
                else backTracking(cnt+1, r+1, 0, papers, left - l*l);
                post(r, c, l);
                papers[l]++;
            }
        }
    }
    
    // r, c를 왼쪽 위 점으로 하여, 크기가 l인 색종이를 붙일 수 있는지 확인하는 method
    static boolean canPost(int r, int c, int l) {
        for (int i = r; i < r + l; i++) {
            for (int j = c; j < c + l; j++) {
                if (!paper[i][j]) return false;
            }
        }
        return true;
    }
    
    // r, c를 왼쪽 위 점으로 하여, 크기가 l인 색종이를 붙이거나 떼는 method
    static void post(int r, int c, int l) {
        for (int i = r; i < r + l; i++) {
            for (int j = c; j < c + l; j++) {
                paper[i][j] ^= true;
            }
        }
    }
}