Algorithm/Baekjoon Online Judge
[Java] BOJ17136_색종이 붙이기
'지훈'
2021. 6. 16. 18:11
https://www.acmicpc.net/problem/17136
브루트포스로 모든 경우를 따져봐야 한다. 이때 각 종류의 색종이가 5개씩 있으므로 색종이를 놓는 도중에 5개 초과로 사용하는 색종이가 있을 경우 가지치기를 통해 경우의 수를 줄일 수 있다. 이 함수가 바로 check함수이다.
처음에 1의 갯수(cnt)를 센 후 색종이를 덮는 함수를 돌려 이 cnt가 0이 됐을 경우 사용한 색종이의 수를 센다.
setpaper함수를 이용하여 색종이를 덮는 것과 덮기 전의 상태로 되돌리는 것 모두 구현했다.
sizeCal함수는 1이 시작되는 위치에서 놓을 수 있는 색종이의 최대 크기를 return 해준다. 만약 그 위치에서 최대 3의 크기의 색종이를 놓을 수 있다면 2, 1의 크기를 가진 색종이도 놓아봐야 한다.
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int[][] arr = new int[10][10];
static int res = Integer.MAX_VALUE;
static int[] paper = new int[6];
static boolean flag = false;
static ArrayList<int[]> list = new ArrayList<>();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = 0;
for (int i = 1; i < 6; i++) {
paper[i] = 5;
}
for (int i = 0; i < 10; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 10; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] == 1) {
list.add(new int[] {i , j});
cnt++;
}
}
}
if(cnt==0) {
System.out.println(0);
return;
}
cover(cnt, 0);
if(res==Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(res);
}
private static void cover(int cnt, int idx) { //cnt남은 1의 개수
if(check()) {
return;
}
if(cnt == 0) {
int temp = 0;
for (int i = 1; i < 6; i++) {
temp += 5-paper[i];
}
res = Math.min(res, temp);
return;
}
int r = list.get(idx)[0];
int c = list.get(idx)[1];
if(arr[r][c] == 1) { //아직 안 덮였다면
int maxSize = sizeCal(r,c);
for (int i = maxSize; i >= 1; i--) {
setPaper(r, c, i, 0); //r c 위치에서 i 크기만큼 0으로 덮어라
paper[i]--;
cover(cnt - i * i, idx+1);
paper[i]++;
setPaper(r, c, i, 1); //r c 위치에서 i 크기만큼 1으로 덮어라 //되돌리기
}
} else cover(cnt, idx+1);
}
private static int sizeCal(int r, int c) {
int size = 5;
while(true) {
if(size == 1) break;
boolean flag = false;
if(r+size > 10 || c+size > 10) {
size--;
continue;
}
for (int i = r; i < r+size; i++) {
for (int j = c; j < c+size; j++) {
if(arr[i][j] == 0) flag = true;
}
if(flag) break;
}
if(!flag) break;
size--;
}
return size;
}
private static boolean check() {
for (int i = 1; i < 6; i++) {
if(paper[i] < 0) return true;
}
return false;
}
private static void setPaper(int r, int c, int size, int type) {
for (int i = r; i < r+size; i++) {
for (int j = c; j < c+size; j++) {
arr[i][j] = type;
}
}
}
}