Algorithm/Baekjoon Online Judge

[Java] BOJ17136_색종이 붙이기

'지훈' 2021. 6. 16. 18:11

https://www.acmicpc.net/problem/17136

 

17136번: 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크

www.acmicpc.net


브루트포스로 모든 경우를 따져봐야 한다. 이때 각 종류의 색종이가 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;
			}
		}
	}

}