[BOJ] 17136. 색종이 붙이기 ★☆

문제

---

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

0

예제 입력 2

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 2

4

예제 입력 3

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 3

5

예제 입력 4

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 4

-1

예제 입력 5

0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 5

7

예제 입력 6

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 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 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 6

4

예제 입력 7

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

예제 출력 7

6

예제 입력 8

0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 0 0 0 0 1

예제 출력 8

5

풀이

---

문제 유형 : 브루트포스, 백트랙킹

1. 완전탐색으로 해결했다. (0,0)부터 칸이 1인지(붙일 수 있는지를) 확인한다.
2. 1이라면 크기 5~1까지의 색종이를 차례로 붙인다.
   2-1. 붙였다면 남은 색종이의 갯수를 뺀 후 다음 열로 넘어간다.
   2-2. 붙인 후에 되돌아왔을 땐 색종이를 떼고 남은 색종이의 갯수를 원상복구한다.
3. 0 이라면 색종이의 갯수 추가 없이 다음 열로 넘어간다.
4. 만약 y==10이 되어 끝에 도달했다면, 행+1, 열=0 을 탐색하도록 한다.
5. 만약 ans보다 cnt가 크다면, 이미 해당 가지는 답이 되지 않으므로 return(중단한다.) - 백트랙킹
6. 끝에 도달했다면 (x==9 && y==10), ans과 cnt 값을 비교해 작은값으로 갱신해주어 출력한다.

코드

---

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

/* 붙일 수 있는 색종이의 최솟값을 찾는 문제
 * 각 색종이는 5장씩
 */
public class Main_bj_17136_색종이붙이기 {
	
	static int ans;
	static int[][] paper;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		paper = new int[10][10];

		StringTokenizer st;
		for (int i = 0; i < 10; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 10; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		ans = 100;		// 최댓값으로 초기화
		int[] remain = new int[] {0, 5, 5, 5, 5, 5};	// 남은 색종이의 갯수
		bp(0, 0, remain, 0);	// 0, 0 부터 붙이기 시작
		
		if(ans==100) ans=-1;
		System.out.println(ans);
		br.close();
	}

	static void bp(int x, int y, int[] remain, int cnt) {
		if(x==9 && y==10) {
			ans = Math.min(ans, cnt);
			return;
		}
		
		if(cnt > ans) return;
		if(y>=10) {
			bp(x+1, 0, remain, cnt);	// 다음 줄로 넘어감
			return;
		}
		
		if(paper[x][y]==1) {	// 색종이를 붙인다
			for(int k=5; k>=1; k--) {	// 5사이즈의 종이부터 붙여본다
				if(isAttach(x, y, k) && remain[k]>0) {
					attach(x, y, k);
					remain[k]--;		// 남은 색종이 갯수 차감
					bp(x, y+1, remain, cnt+1);	// 다음 칸으로
					detach(x, y, k);	
					remain[k]++;		// 원상복구
				}
			}
		}
		else {	// 다음 칸으로 
			bp(x, y+1, remain, cnt);
		}
	}
	
	// size 만큼의 색종이를 붙일 수 있는지 확인하는 과정
	static boolean isAttach(int x, int y, int size) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				if(i>=10 || j>=10 || paper[i][j]!=1) return false;
			}
		}
		return true;
	}
	
	// 색종이를 붙이는 과정
	static void attach(int x, int y, int size) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				paper[i][j] = 2;	
			}
		}
	}
	
	// 색종이를 뗴는 과정
	static void detach(int x, int y, int size) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				paper[i][j] = 1; 
			}
		}
	}

}