색종이 붙이기


백준 [17136] 색종이 붙이기

문제보기
Alt text

소스코드

import java.util.Scanner;

public class Main {
	static int[][] map;
	static boolean[][] visited;
	static int ans, one;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		map = new int[10][10];
		visited = new boolean[10][10];
		ans = 987654321;
		one = 0;

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

		int[] paper = { 5, 5, 5, 5, 5 };
		if (one != 0) {
			attach(paper, 0, 0, one, 0);
			if (ans == 987654321)
				ans = -1;
		} else
			ans = 0;
		System.out.println(ans);
	}

	public static void attach(int[] paper, int x, int y, int cnt, int used) {
		if (cnt == 0) {
			ans = Math.min(ans, used);
			return;
		}
		if (used >= ans)
			return;

		for (int i = x; i < 10; i++) {
			for (int j = y; j < 10; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					boolean flag = false; // 색종이 붙이기 가능 여부
					for (int k = 0; k < 5; k++) {
						if (paper[k] != 0) {
							if (isOk(k + 1, i, j)) {
								flag = true;
								visitChk(true, k + 1, i, j);
								paper[k] -= 1;
								cnt -= ((k + 1) * (k + 1));
								used++;
								attach(paper, x, y, cnt, used);
								visitChk(false, k + 1, i, j);
								paper[k] += 1;
								cnt += ((k + 1) * (k + 1));
								used--;
								flag = false;
							}
						}
					}
					if (!flag)
						return;
				}
			}
		}
	}

	public static boolean isOk(int size, int x, int y) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (isRange(i, j) && map[i][j] == 1 && !visited[i][j]) {
					continue;
				} else {
					return false;
				}
			}
		}
		return true;
	}

	public static void visitChk(boolean v, int size, int x, int y) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				visited[i][j] = v;
			}
		}
	}

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