BOJ - 17136 ) 색종이 붙이기

---

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

17136번: 색종이 붙이기

 

 

---

한참 시간초과가 난문제..

 

색종이를 붙일수있으면 ( 5x5,4x4...) 붙이고 최소로 덮을 수 있는 개수를 출력하는 

 

문제이다. 

 

각 색종이는 5장씩있어서 5장이 넘어가서 덮는 경우에는 -1을 출력한다.

 

처음에 완전탐색으로 모든경우( 최적해를 구하기위해 ) 를탐색했는데 자꾸 시간초과가 났다.

 

가장 큰 것부터 붙이기 때문에 그리디한 해가 가장 먼저 나오게된다.

 

탐색을 돌다가 그 해가 넘어가는 경우는 함수를 바로 끝내주어야한다 ( 백트래킹 )

 

이 수를 생각못해서 3시간넘게 고민했던거같다 ..ㅠ

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int map[][] = new int[11][11];
    static int color_square[] = {5, 5, 5, 5, 5, 5};
    static int ans = Integer.MAX_VALUE;
    static boolean visit[][] = new boolean[11][11];
    
    public static void input()throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int y = 0;y < 10 ;y ++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int x = 0; x <10 ; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }
    }
    
    public static void main(String[] args) throws Exception{
        input();
        square(0,0);
        if(ans != Integer.MAX_VALUE)System.out.println(ans);
        else System.out.println(-1);
    }
 
    public static void square(int pos, int cnt) {
        int y = pos/10;
        int x = pos%10;
        if(ans <= cnt) return;
        if(pos ==100) {
            if(check()){
                int res = 0;
                for (int i : color_square)res += (5-i);
                ans = Math.min(ans, res);
                return;
            }
        }
        
        if(map[y][x] == 1) {
            for(int color = 5; color > 0 ; color-=1 ) {
                if(color_simul(y,x,color) && color_square[color] > 0) { // 채울수 있으면?
                    color_fill(y,x,color,0); // 1로 채우고
                    color_square[color]--;   // color번째 요소를 감소 시킨다.
                    square(pos+1,cnt+1);
                    color_fill(y,x,color,1); // 갔다왔으니 0으로 채우고 
                    color_square[color]++;   // 다시 증가시킨다.
                }
            }    
        }
        
        else square(pos+1,cnt);
        
    }
    public static boolean check() {
        for(int y = 0; y <10  ; y++) {
            for(int x = 0; x <10; x++) {
                if(map[y][x] == 1) return false;
            }
        }
        return true;
    }
 
    public static void color_fill(int y, int x, int color, int i) {
        for(int y_ = y; y_ < y+color ; y_++) {
            for(int x_ = x; x_ <x+color; x_++) {
                if(y_ < 10 && x_<10) map[y_][x_] = i;
            }
        }
    }
 
    public static boolean color_simul(int y, int x, int color) {
        if(y + color > 10 || x + color > 10) return false;
        for(int y_ =y ; y_ < y+color ; y_++) {
            for(int x_=x ; x_ < x+color ; x_++) {
                if(y_ < 10 && x_< 10 && map[y_][x_] ==0) return false;
            }
        }
        return true;
    }
 
}

---