문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.
예제 입력 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 1
0예제 입력 2
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 2
4예제 입력 3
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 3
5예제 입력 4
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 4
-1예제 입력 5
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0예제 출력 5
7풀이
이 문제는 DFS 알고리즘을 이용해서 모든 경우의 수를 다 구해봐야 풀 수 있는 문제이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static int[][] map = new int[10][10];
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0; i<10; i++) {
String[] input = br.readLine().split(" ");
for(int j=0; j<10; j++) {
map[i][j] = Integer.parseInt(input[j]);
}
}
int[] papers = new int[6];
dfs(0, papers);
if(min==Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(min);
}
static void dfs(int row, int[] paper_used) {
if(check()) {
int cnt = 0;
for(int i=1; i<=5 ; i++) {
cnt += paper_used[i];
}
if(min > cnt)
min = cnt;
return;
}
for(int i=row; i<10; i++) {
for(int j=0; j<10; j++) {
if(map[i][j] == 1) {
for(int paper = 5 ; paper >= 1; paper--) {
if(paper_used[paper] < 5 && canAttach(i, j, paper)) {
paper_used[paper]++;
attach(i, j, paper);
dfs(i, paper_used);
recover(i, j, paper);
paper_used[paper]--;
}
}
return;
}
}
}
}
static boolean canAttach(int x, int y, int paper) {
for(int i=0; i<paper; i++) {
for(int j=0; j<paper; j++) {
if(!(x+i>=0 && x+i<10 && y+j>=0 && y+j<10))
return false;
if(map[x+i][y+j] == 0)
return false;
}
}
return true;
}
static void attach(int x, int y, int paper) {
for(int i=0 ; i<paper; i++) {
for(int j=0; j<paper; j++) {
map[x+i][y+j] = 0;
}
}
}
static void recover(int x, int y, int paper) {
for(int i=0; i<paper; i++) {
for(int j=0; j<paper; j++) {
map[x+i][y+j] = 1;
}
}
}
static boolean check() {
for(int i=0; i<10; i++) {
for(int j=0; j<10 ; j++) {
if(map[i][j] == 1)
return false;
}
}
return true;
}
}
👶🏻Jr. Programmer