[백준 17136] 색종이 붙이기

 

DFS + 백트래킹 활용 문제이며,

색종이를 최소한으로 사용하려면 큰 종이부터 사용해야 한다는 점에서 그리디한 방식도 섞여있다.

 

1. 색종이 개수 정보를 담은 배열을 만든다.

2. 10x10 배열을 탐색하며 값이 1일 경우 5x5, 4x4, ..., 1x1 순으로 검사하며 붙일 수 있다면 붙인다.

3. 1을 모두 메꿀 수 없다면 최소값 갱신이 안되므로 -1을 출력한다.

4. DFS 도중 이미 최소값보다 색종이 사용 수가 크다면 함수를 종료해준다.

 

제한시간이 1초라서 가지치기를 해주었다.

 

public class Main {
    
    static int paper[] = {0, 5, 5, 5, 5, 5};
    static int a[][] = new int[10][10];
    static int min = 100;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for(int i=0; i<10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<10; j++)
                a[i][j] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0);
        System.out.println(min == 100 ? -1 : min);
    }
    
    public static void dfs(int idx, int cnt) {
        if(idx == 100) {
            min = Math.min(min, cnt);
            return;
        }
        int r = idx/10;
        int c = idx%10;
        
        if(min <= cnt) return;
        
        if(a[r][c] == 1) {
            for(int i=5; i>0; i--) {
                if(paper[i] > 0) {
                    if(check(r, c, i)) {
                        fill(r, c, i, 0);
                        paper[i]--;
                        dfs(idx+1, cnt+1);
                        fill(r, c, i, 1);
                        paper[i]++;
                    }
                }
            }
        } else dfs(idx+1, cnt);
    }
    
    public static boolean check(int r, int c, int len) {
        if(r + len > 10 || c + len > 10) return false;
        for(int i=r; i<r + len; i++)
            for(int j=c; j<c + len; j++)
                if(a[i][j] == 0) return false;
        return true;
    }
    
    public static void fill(int r, int c, int len, int status) {
        for(int i=r; i<r + len; i++)
            for(int j=c; j<c + len; j++)
                a[i][j] = status;
    }
}