[백준, BOJ 17136] 색종이 붙이기 (java)

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

17136번: 색종이 붙이기

---

문제

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

<그림 1>

색종이를 크기가 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

---

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

public class Main {
	
	static int[][] arr; // 10 x 10 종이
	static int[] numOfPaper = new int[] {0, 5, 5, 5, 5, 5}; // 각 색종이는 5개씩
	static int result = Integer.MAX_VALUE; // 답
	static int count;
	
	private static void pasting(int x, int y) { // 색종이 붙이는 메소드
		
		if(x >= 10 || y >= 10) { // 색종이를 가능한 다 붙였다면
			for (int i = 0; i < 10; i++) { // 못 붙인 곳이 있는지 검사
				for (int j = 0; j < arr.length; j++) {
					if(arr[i][j] == 1) return; // 못 붙인 곳 있다면 리턴
				}
			}
			result = Math.min(result, count); // 최소값 저장
			return;
		}
		
		if(arr[x][y] == 0) { // 현재 위치가 0이라면
			while(x < 10 && y < 10 && arr[x][y] == 0) { // 1인 곳을 찾아서
				if(y < 9) y++;
				else {
					x++;
					y = 0;
				}
			}
			pasting(x, y); // 재귀
			return;
		}
		
		for (int i = 5; i > 0; i--) { // 붙일 수 있는 모든 사이즈의 색종이를 붙여본다
			if(numOfPaper[i] > 0 && coloredPaper(i, x, y)) { // 현재 사이즈의 색종이를 붙일 수 있다면
				numOfPaper[i]--; // 색종이 개수 줄여주고
				count++; // 붙인 색종이 개수 늘려주고
				if(y == 9) pasting(x + 1, 0); // 재귀
				else pasting(x, y + 1);
				numOfPaper[i]++; // 다음 색종이를 확인하기 위해 다시 색종이 개수 늘려주고
				count--; // 붙인 색종이 개수 줄여주고
				return1(i, x, y); // 색종이 다시 붙여줌
			}
		}
	}
	
	private static boolean coloredPaper(int size, int x, int y) { // size 크기의 색종이 붙이는 메소드
		// 범위를 벗어나면 false 리턴
		if(x + size - 1 >= 10 || y + size - 1 >= 10) return false;
		
		boolean check = true; // size 크기의 색종이를 붙일 수 있는지 체크
for1:	for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if(arr[i][j] == 0) { // size 크기 안에 0이 있다면
					check = false;
					break for1;
				}
			}
		}

		if(!check) return false; // 붙일 수 없으면 false 리턴
		else { // 붙일 수 있다면
			for (int i = x; i < x + size; i++) { // 붙이고
				for (int j = y; j < y + size; j++) {
					arr[i][j] = 0;
				}
			}
			return true; // true 리턴
		}
	}
	
	static void return1(int size, int x, int y) { // size 크기의 색종이 붙인 것을 다시 되돌리는 메소드
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				arr[i][j] = 1;
			}
		}

	}
	
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 입력
		arr = new int[10][10];
		for (int i = 0; i < 10; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 10; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 색종이 붙이기
		pasting(0, 0);
		
		// 출력
		if(result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

}