백준 [17136] 색종이 붙이기
문제보기
소스코드
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;
}
}