반응형
문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
<그림 1>
색종이를 크기가 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
예제 입력 6
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
예제 출력 6
4
예제 입력 7
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 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 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
예제 출력 7
6
예제 입력 8
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 1 1 0 0 0
0 1 1 1 0 0 0 0 0 1
예제 출력 8
5소스코드
package 백트래킹;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_17136_색종이붙이기 {
private static BufferedReader bf;
private static StringTokenizer st;
private static int [][] map;
private static int [] papers= {0,5,5,5,5,5};
private static int paperCnt=Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
bf=new BufferedReader(new InputStreamReader(System.in));
map=new int[10][10];
for(int r=0;r<10;r++) {
st=new StringTokenizer(bf.readLine());
for(int c=0;c<10;c++) {
map[r][c]=Integer.parseInt(st.nextToken());
}
}
dfs(0,0,0);
if(paperCnt==Integer.MAX_VALUE) paperCnt=-1;
System.out.println(paperCnt);
}
public static void dfs(int r, int c, int cnt) {
if(r>=9 && c==10) {
paperCnt=Math.min(paperCnt, cnt);
return;
}
if(cnt>=paperCnt) return;
if(c==10) { // 아래줄로 이동
dfs(r+1,0,cnt);
return;
}
if(map[r][c]==1) {
for(int i=5;i>0;i--) {
if(papers[i]>0 && coverCheck(r,c,i)) {
cover(r,c,i, 0); // 색종이를 붙임
papers[i]--;
dfs(r,c+1,cnt+1);
cover(r,c,i,1); // 색종이를 뗌
papers[i]++;
}
}
} else { // 오른쪽으로 이동
dfs(r,c+1,cnt);
return;
}
}
// n*n 색종이로 덮을 수 있는 지 확인
public static boolean coverCheck(int r, int c, int n) {
for(int x=r;x<r+n;x++) {
for(int y=c;y<c+n;y++) {
if(!isIn(x,y) || map[x][y]!=1) return false;
}
}
return true;
}
// 덮기
public static void cover(int r, int c, int n, int state) {
for(int x=r;x<r+n;x++) {
for(int y=c;y<c+n;y++) {
map[x][y]=state;
}
}
}
public static boolean isIn(int r, int c) {
return r>=0 && r<10 && c>=0 && c<10;
}
}10X10 크기의 색종이 전체를 탐색하며 백트래킹을 수행합니다.
반응형
'코딩테스트 > 백트래킹' 카테고리의 다른 글
| [Java] 백준 9663번 : N-Queen (0) | 2022.04.17 |
|---|---|
| [Java] 백준 15684번 : 사다리 조작 (0) | 2022.04.13 |