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

백준의 색종이 붙이기 문제를 풀어보았다.(Java)

 

구현에 사용한 알고리즘은 Backtracking이다.

 

백트래킹 문제로 1x1, 2x2, 3x3, 4x4, 5x5로 이루어진 색종이 5개를 이용하여

1이 적힌 모든 칸을 색종이로 덮는 문제이다.

BOJ1987 문제의 심화 버전인 것 같다. 5x5부터 비교하여 최대한 색종이를 적게 사용하도록 한다.

보드의 마지막에 도착하면 가장 작은 값을 초기화 한다.

 

작성한 코드는 아래와 같다.

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ17136 {
	static int[][] grid = new int[10][10];
	static int result;
	static int paper[] = {0, 5, 5, 5, 5, 5};

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

		for(int i = 0; i < 10; i++) {
			String[] temp = br.readLine().split(" ");
			for(int j = 0; j < 10; j++) {
				grid[i][j] = Integer.parseInt(temp[j]);
			}
		}

		result = Integer.MAX_VALUE;
		paper(0, 0, 0);

		if(result == Integer.MAX_VALUE) {
			result = -1;
		}
		System.out.println(result);
	}

	public static void paper(int x, int y, int count) {
		if(x >= 9 && y > 9) {
			result = Math.min(result, count);
			return;
		}

		if(count >= result)
			return;

		if(y > 9) {
			paper(x + 1, 0, count);
			return;
		}

		if(grid[x][y] == 1) {
			for(int i = 5; i >= 1; i--) {
				if(paper[i] > 0 && isAttach(x, y, i)){
					attach(x, y, i, 0);
					paper[i]--;
					paper(x, y + 1, count + 1);
					paper[i]++;
					attach(x, y, i, 1);
				}
			}
		}
		else {
			paper(x, y + 1, count);
		}

	}

	public 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 < 0 || i >= 10 || j < 0 || j >= 10) {
					return false;
				}
				if(grid[i][j] != 1) {
					return false;
				}
			}
		}
		return true;
	}

	public static void attach(int x, int y, int size, int compare) {
		for(int i = x; i < x + size; i++) {
			for(int j = y; j < y + size; j++) {
				grid[i][j] = compare;
			}
		}
	}
}