백준 17136 색종이 붙이기

문제

---

17136번: 색종이 붙이기 (acmicpc.net)

해결방법

---

• 그리디 처음에 문제를 보고 크기가 큰 색종이 부터 순서대로 넣으면 되지않을까 → X 아래와 같은 반례 존재

  0 0 0 0 0 0 0 0 0 0
  0 0 1 1 1 1 1 1 0 0
  0 0 1 1 1 1 1 1 0 0
  0 0 1 1 1 1 1 1 0 0
  0 0 1 1 1 1 1 1 0 0
  0 0 1 1 1 1 1 1 0 0
  0 0 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 0
  0 0 0 0 0 0 0 0 0 0
  
  // Answer = 4

• 순열을 통해 크기 별로 색종이를 씌우면 되지 않을까 → X 아래와 같은 반례 존재

  1 1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 0 0 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 0 0 0 0 0
  1 1 1 1 1 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  
  // Answer = 5

  • 색종이를 씌울 때 항상 왼쪽 위부터 가능한 위치에는 다 씌우면서 했기 때문에 위 반례를 계산할 수 없었음
• 모든 배열을 돌면서 붙일 수 있는 색종이를 다붙여 보며 DFS를 수행한다 → O

동작과정

---

1. 종이의 왼쪽 맨 위 부터 탐색을 시작한다.
2. 현재 탐색중인 위치가 1이면 크기가 5부터 1까지인 색종이 중 붙일 수 있으면 붙이고 다음 탐색을 수행한다.
   • 큰거 부터 붙여보는 이유는 그리디한 방법으로 5부터 붙이면 더 빨리 최솟값을 찾아 가지치기를 수행할 수 있지 않을까 하는 생각
   • 각 크기의 색종이는 5번만 사용해야 하므로 papers 를 통해 사용 횟수를 검사한다.
3. 현재 위치 탐색이 끝나면 오른쪽을 탐색하고 맨 오른쪽까지 오면 다음 줄을 탐색한다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

/*
 * 	1. 왼쪽 위 부터 돌면서 큰 색종이 부터 붙일 수 있으면 다 붙이기 ( 그리디한 방법 ) -> X
 * 	2. 순열을 이용해 사이즈 별로 색종이 다 붙여보기 -> X
 *	3. DFS를 이용해 완전 탐색하면서 size를 큰거 부터 붙였다가 땟다가 하면서 가장 작은 종이 수 찾기 -> O
 */
public class Main {

	private static int result = Integer.MAX_VALUE;
	private static int[][] map;
	private static int[] papers;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

		map = new int[10][10];
		for (int i = 0; i < 10; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < 10; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		
		papers = new int[6];
		
		find(0, 0, 0);
		
		// 답을 못찾았으면 -1을 출력함
		out.write(result == Integer.MAX_VALUE ? "-1" : result+"");
		out.flush();
	}

	// DFS, 현재 위치가 1이면 size를 5부터 1까지 해서 종이를 붙여보고 다음 DFS로
	private static void find(int y, int x, int cnt) {
		
		// 이미 구한 최솟값보다 cnt 가 커지면 더이상 탐색할 필요가 없음
		if(cnt >= result)
			return;
		
		// 마지막에 도달했다면 최솟값을 갱신
		if(y == 9 && x == 10)
			result = Math.min(cnt, result);
		
		// 오른쪽 끝까지 탐색했다면 한칸아래의 맨 처음 부터 탐색함
		if(x == 10) {
			find(y+1, 0, cnt);
			return;
		}
		
		// 현재 위치가 1이면 size 5 ~ 1 까지의 색종이를 붙여본다.
		if(map[y][x] == 1) {
			for(int size = 5; size > 0; size--) {
				// 해당 size의 색종이를 아직 5번보다 적게 이용했고 해당 위치에 붙일 수 있다면
				if(papers[size] < 5 && canUseSize(map, y, x, size)) {
					// 해당 size의 색종이를 사용했다고 표시하고 맵에 표시
					papers[size]++;
					setMap(map, y, x, size, 0);
					find(y, x, cnt+1);
					// 다시 원상태로 복구
					setMap(map, y, x, size, 1);
					papers[size]--;
				}
			}
		}
		// 오른쪽 칸 탐색
		else {
			find(y, x+1, cnt);
		}
	}

	// y, x의 위치에 size에 해당하는 색종이를 붙일 수 있는지
	private static boolean canUseSize(int[][] map, int y, int x, int size) {

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (!isInBound(i + y, j + x) || map[i + y][j + x] == 0) {
					return false;
				}
			}
		}

		return true;
	}

	// map의 y, x 부터 size 만큼을 value로 바꿈
	private static void setMap(int[][] map, int y, int x, int size, int value) {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				map[y + i][x + j] = value;
			}
		}
	}

	// 경계 체크
	private static boolean isInBound(int y, int x) {
		return x >= 0 && x < 10 && y >= 0 && y < 10;
	}
}