[백준] 17136 색종이 붙이기 - Java

 

 

 

붙이는 개수가 최소가 돼야 한다.

크기가 큰 색종이부터 쓰면 최소 개수를 구할 수 있다.

 

스도쿠 문제를 풀 때 처럼 좌측 상단에서 우측 하단으로 내려가면서 탐색한다.

 

색종이로 덮는 작업과 덮은걸 치우는 작업은 따로 메서드로 만들어서 진행하자.

 

사용할 수 있는 색종이의 수가 정해짐에 유의하고 백트래킹을 돌리면 된다.

 

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    static int[][] map = new int[10][10];
    static int ans = Integer.MAX_VALUE;
    static int[] remain = {0, 5, 5, 5, 5, 5};

    static StringBuilder sb = new StringBuilder();

    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++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bt(0,0,0);

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);        

        
       

    }

    static void bt(int r, int c, int cnt){
        if(r == 10){
            ans = Math.min(ans, cnt);            
            return;
        }
        
        if(c == 10){
            bt(r + 1, 0, cnt);
            return;
        }
        

        if(cnt >= ans){
            return;
        }

        if(map[r][c] == 1){
            for(int i = 5; i >= 1; i--){
                if(isCover(r, c, i) && remain[i] > 0){
                    cover(r, c, i);
                    remain[i]--;
                    bt(r, c + 1, cnt + 1);
                    undo(r, c, i);
                    remain[i]++;
                }
            }
        }else if (map[r][c] == 0 || map[r][c] == -1){
            bt(r, c + 1, cnt);
        }
        

    }

    static boolean isCover(int r, int c, int size){
        for(int i = r; i< r + size; i++){
            for(int j = c; j < c + size; j++){
                if(i >= 10 || j >= 10){
                    return false;
                }

                if(map[i][j] != 1){
                    return false;
                }
            }
        }

        return true;
    }

    static void cover(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] = -1;
            }
        }
    }

    static void undo(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] = 1;
            }
        }
    }
}