[Gold II] 색종이 붙이기 - 17136
성능 요약
메모리: 22020 KB, 시간: 344 ms
분류
백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing)
문제 설명
<그림 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을 출력한다.
풀이
그리디적으로 접근하면 최소값을 찾을 수 없기 때문에 완전 탐색으로 dfs를 구현하였다.
map이 1인 경우에 해당 색종이로 색칠이 가능하면 칠해주고 (1을 0으로 바꿈) dfs를 반복한다.
중요한 점은 다시 map을 원상복구하고(0을 1로 바꿈), 색종이의 개수도 초기화한 후 다음 색종이를 칠하면서 dfs를 계속해야 한다는 점이다.
그리고 중간에 return을 걸지 않으면 탐색 가능한 색종이가 없음에도 계속해서 함수가 반복되어 무한루프에 빠진다.
import java.util.Scanner;
public class Main {
static int[][] map = new int[10][10];
static boolean[][] visited = new boolean[10][10];
static int[] confetti = { 0, 5, 5, 5, 5, 5 };
static int ans = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
map[i][j] = sc.nextInt();
put(0);
if (ans == Integer.MAX_VALUE)
ans = -1;
System.out.println(ans);
}
static void put(int cnt) {
boolean check = true;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
check = false;
break;
}
}
if (check) {
ans = Math.min(ans, cnt);
return;
}
if (cnt >= ans)
return;
// 5부터 가능한지 검사하기
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++) {
if (map[i][j] == 1) {
for (int c = 5; c > 0; c--)
if (check(i, j, c)) {
if (confetti[c] == 0)
continue;
confetti[c]--;
color(i, j, c);
put(cnt + 1);
confetti[c]++;
color(i, j, c); // 원상 복구하기
}
return;
}
}
}
static boolean check(int i, int j, int size) {
for (int r = i; r < i + size; r++) {
for (int c = j; c < j + size; c++) {
if (r >= 10 || c >= 10 || map[r][c] == 0 || visited[r][c]) {
return false;
}
}
}
return true;
}
static void color(int i, int j, int size) {
for (int r = i; r < i + size; r++) {
for (int c = j; c < j + size; c++) {
map[r][c] = (map[r][c] + 1) % 2;
}
}
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 9466 - 텀 프로젝트 (자바 Java) (0) | 2022.10.17 |
---|---|
[백준] 17281 - ⚾ (자바 Java) (1) | 2022.10.13 |
[백준] 1931 - 회의실 배정 (자바 Java) (0) | 2022.10.12 |
[백준] 2206 - 벽 부수고 이동하기 (자바 Java) (0) | 2022.10.07 |
[백준] 16235 - 나무 재테크 (자바 Java) (1) | 2022.10.07 |