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

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

17136번: 색종이 붙이기

---

처음 이 문제를 풀 때에는 1을 만나면 거기서부터 붙일 수 있는 가장 큰 색종이를 붙이면 된다고 생각했습니다.

하지만 다음 예제를 생각해보면

• 좌표 (1, 1) 에서 길이 5짜리 색종이를 붙입니다. (사용한 총 색종이 : 1장)

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

 

• (1, 6) 좌표에서 길이 3짜리 색종이를 붙입니다. (사용한 총 색종이 : 2장)

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

 

 

• (4, 6) 좌표에서 길이 3짜리 색종이를 붙입니다. (사용한 총 색종이 : 3장)

 

 

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

• (5, 1) 좌표에서 길이 2짜리 색종이 2 장을 붙입니다. (사용한 총 색종이 : 5장)

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

 

• (6, 5) 좌표에서 길이 1짜리 색종이 5장을 붙입니다. (사용한 총 색종이 : 10장)

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

 

이렇게 하면 사용한 색종이가 총 10 장이 되는데, 정답은 길이 4짜리 색종이를 4개 붙이면 됩니다. 그렇기 때문에 좌표에서 1을 만나게 되면 길이 5짜리 부터 붙일 수 있는지 확인하고, 붙일 수 없다면 길이 4, 3, 2, 1 순으로 확인하여 붙이고 다음으로 넘어가는 재귀적인 방법으로 모든 길이의 색종이를 붙여봤을 때 최소값을 구하는 방법으로 접근해야 합니다.

[ 문제 풀이 ]

1. 길이 1부터 5까지 색종이를 나타내는 paper 배열에 1 번째 인덱스부터 5 번째 인덱스까지 5를 저장해줍니다.

2. 이제 DFS(x 좌표, y 좌표, 사용한 색종이의 개수) 를 시작하는데 (0, 0) 좌표부터 진행합니다.

(1) 재귀를 빠져나가는 기저조건은 좌표가 (10, 10) 까지 갔을 때와 사용한 색종이 개수 cnt 를 최소로 하는 것이 정답이기 때문에 cnt 가 최솟값 answer 보다 커지게 되면 재귀를 종료합니다.

(2) 2차원 배열에서 1을 만나면 색종이를 붙여보는데 길이 5 짜리 부터 1 짜리 까지 붙입니다. 여기서 주의해야 할점은 papering(x 좌표, y좌표, 사용할 색종이의 길이, 2차원 배열에 표시할 변수) 로 색종이를 붙여주고 사용한 길이의 색종이를 -1 해주는데, 색종이를 붙이면 그 자리의 좌표를 0으로 하고 붙이고 나서는 그 자리를 다시 1로 붙여놔야 다음 길이의 색종이를 한번 더 붙여볼 수 있습니다. 그래서 papering(r, c, i, 0) (길이 i 짜리 색종이 붙이기) -> paper[i] -- (길이 i짜리 색종이 -1) -> DFS -> papering(r, c, i, 1) (길이 i짜리 붙인 색종이 떼기) -> paper[i] ++ (사용한 색종이 복귀) 순서로 해줘야 합니다.

3. 이렇게 재귀적으로 완전탐색하면서 좌표가 (10, 10) 이 됐을 때 answer 에 사용한 색종이 cnt 의 최솟값을 비교해주면서 저장하면 정답입니다.

---

import java.util.Scanner;

public class Main {


	static int[][] map = new int[10][10];
	static int[] paper = {0,5,5,5,5,5};
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		for(int i=0; i<10; i++) {
			for(int j=0; j<10; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		DFS(0, 0, 0);
		
		System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
	}

	public static void DFS(int r, int c, int cnt) {

		if(r >= 9 && c > 9) {
			answer = Math.min(answer, cnt);
			return;
		}

		if(answer <= cnt) return;

		if(c > 9) {
			DFS(r+1, 0, cnt);
			return;
		}

		if(map[r][c] == 1) {
			for(int i=5; i>=1; i--) {
				if(paper[i] > 0 && check(r, c, i)) {
					papering(r, c, i, 0);
					paper[i]--;
					DFS(r, c+1, cnt+1);
					papering(r, c, i, 1);
					paper[i]++;
				}
			}
		} else DFS(r, c+1, cnt);
	}

	public static void papering(int x, int y, int size, int state) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				map[i][j] = state;
			}
		}
	}
 
	public static boolean check(int x, int y, int size) {
		for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				if(!isInside(i, j) || map[i][j] != 1) return false;
			}
		}
		return true;
	}

	public static boolean isInside(int x, int y) {
		return x>=0 && x<10 && y>=0 && y<10;
	}

}