백트래킹, 브루트 포스 문제.
한 변의 길이가 1, 2, 3, 4, 5 인 정사각형 모양의 색종이를
한 변의 길이가 10 인 색종이 안에 붙이되, 다음 조건을 만족해야 한다.
1. 0이 적힌 칸에는 색종이가 있어서는 안된다.
2. 종이의 경계 밖을 나가서는 안된다.
3. 붙이는 종이들끼리 겹치면 안된다.
이 때 1이 적힌 모든 칸들을 붙이는데 필요한 색종이의 최소 개수를 구하면 된다.
- 현재의 위치와 사용된 종이의 총 개수를 인자로 넘겨주며 DFS 함수를 재귀호출하면 될 것 같다.
- 남아있는 종이의 개수를 나타내는 int[] paperArr
- DFS (x, y, 현재 사용한 종이 장수)
- 만약 끝에 도착했으면 최소 개수를 최신화한다.
- 현재 개수가 최소 개수보다 많으면 더 볼 필요가 없기 때문에 return.
- 오른쪽 끝이면 (y==9) 다음줄로 넘어간다. (y=0, x++)
- 종이를 순차탐색하던 중 1을 만나면
- 해당 좌표를 꼭지점으로, 가장 큰 종이(5x5) 부터 가장 작은 종이(1x1)까지 붙이기를 시작한다.
- 종이의 잔여량이 충분한지 확인한다.
- 붙일 수 있는지 확인한다.
- 종이 밖으로 나가는지 확인한다.
- 0과 닿는지 확인한다.
- 색종이를 붙이면 해당 종이의 남은 종이 장수--
- DFS (x, y+1, 현재 사용한 종이 장수 + 1)
- DFS 가 끝나면 해당 종이의 남은 종이 장수++
- 1을 만난게 아니면 오른쪽으로 한 칸 간다. (y++)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int answer = Integer.MAX_VALUE;
static int[] paperArr = {5, 5, 5, 5, 5};
static int[][] board;
public static void attach(int x, int y, int size){
for(int i=x; i<(x+size); i++){
for(int j=y; j<y+size; j++){
board[i][j] = 0;
}
}
}
public static void detach(int x, int y, int size) {
for (int i=x; i<(x+size); i++) {
for (int j = y; j < y + size; j++) {
board[i][j] = 1;
}
}
}
public static boolean isAttachable(int x, int y, int size){
for(int i=x; i<(x+size); i++){
for(int j=y; j<(y+size); j++){
if(i<0 || j<0 || i>9 || j>9){
return false;
}
if(board[i][j] != 1) return false;
}
}
return true;
}
public static void DFS(int x, int y, int count){
if(x>=9 && y>9){
answer = Math.min(count, answer);
return;
}
if(count>=answer) return;
if(y>9){
DFS(x + 1, 0, count);
return;
}
if(board[x][y] == 1){
for(int i=5; i>=1; i--){
if(paperArr[i-1]>0 && isAttachable(x, y, i)){
attach(x, y, i);
paperArr[i-1]--;
DFS(x, y+1, count+1);
detach(x, y, i);
paperArr[i-1]++;
}
}
}else{
DFS(x, y+1, count);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
board = new int[10][10];
StringTokenizer stk;
for(int x=0; x<10; x++){
stk = new StringTokenizer(br.readLine());
for(int y=0; y<10; y++){
board[x][y] = Integer.parseInt(stk.nextToken());
}
}
DFS(0, 0, 0);
if (answer == Integer.MAX_VALUE) answer = -1;
System.out.println(answer);
}
}
'Solved > BOJ' 카테고리의 다른 글
[백준 16987] 계란으로 계란치기 (0) | 2023.05.06 |
---|---|
[백준 9663] N-Queen (0) | 2023.05.05 |
[백준 11053] 가장 긴 증가하는 부분수열 (0) | 2023.05.03 |
[백준 1912] 연속합 (0) | 2023.05.02 |
[백준 10816] 숫자 카드 2 (0) | 2023.04.30 |