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

[문제링크]

17136번: 색종이 붙이기

 

0. 큰 색종이부터 차례대로, 모든 붙일수 있는 부분에 붙여보고 떼어보며 진행하는 brute-force 문제

chk함수 : n*n 공간이 전부 1이면, 색종이를 붙일 수 있으면 true를 반환

remove : n*n 색종이를 붙이는 함수, 모든 1을 0으로 전환

repair : n*n 색종이를 떼는 함수, 모든 0을 1로 전환

 

1. 10*10 색종이의 모든 가능한 n*n 공간을 검사하며 색종이를 붙여보고, 더이상 붙일 수 없다면 n-1번째 색종이로 넘어가서 붙여보기를 시도한다.

 

2. 가지치기 1 : 앞으로 사용 가능한 모든 색종이를 사용해도 현재 남아있는 1의 갯수를 다 덮을만큼 충분하지 않다면, 포기하고 돌아간다.

 

3. 가지치기 2 : 이전 연산에서 구했던 해답보다 더 많은 색종이를 이미 사용했다면, 포기하고 돌아간다

 

4. min은 최대 25이므로, 그 이상의 값을 초깃값으로 지정한 후 갱신되지 않았다면 -1을 출력, 아니면 갱신된 값을 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		map=new int[10][10];
		int num=0;
		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());
				if(map[i][j]==1)num++;
			}
		}
		
		min=Integer.MAX_VALUE;
		search(0,0,0,5, num);
		System.out.println(min==Integer.MAX_VALUE?-1:min);
	}
	static int min;
	static int[][]map;
	static int limit[]=new int[] {0,5,5,5,5,5};
	static int[] maximunArea= {0,0,5,20,45,80};
	
	static void search(int x, int y, int cnt, int k, int num) {
    
		//가지치기
		//앞으로 쓸수잇는 모든 색종이를 다 써도 모든 1을 덮을수 없다면, 돌아간다
		if(maximunArea[k]+k*k*limit[k] < num) {
			return;
		}
		//다른 정답에서 구한 min값보다 이미 많은 수의 색종이를 썼다면, 돌아간다
		if(cnt>=min)return;
		//1을 다 붙였으면 min 갱신 후, 돌아간다
		if(num==0) {
			min=min<cnt?min:cnt;
			return;
		}
		//다 붙이는데 실패했다면, 돌아간다.
		if(k==0)return;
		
        
		
		for (int i = x; i < 11-k; i++) {
			for (int j = 0; j < 11-k; j++) {
				if(map[i][j]==1 && limit[k]>0) {
					if(chk(i,j,k)) {
						//제거
						remove(i,j,k);
						limit[k]--;
						//그 위치부터 다시 재귀
						
						search(i,j,cnt+1,k, num-k*k);
						
						//복구
						repair(i,j,k);
						limit[k]++;
					}
				}
			}
		}
		
		
		search(0,0,cnt,k-1, num);
		
	}
	
	static boolean chk(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				if(map[i][j]==0)return false;
			}
		}
		return true;
	}
	static void remove(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				map[i][j]=0;
			}
		}
	}
	static void repair(int x, int y, int k) {
		for (int i = x; i < x+k; i++) {
			for (int j = y; j < y+k; j++) {
				map[i][j]=1;
			}
		}
	}
	
}

결과 화면