색종이 붙이기 (17136)
1. 문제
설명
<그림 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을 출력한다.
2. 풀이
백트래킹을 이용해서 색종이를 붙이는 모든 경우를 탐색하는 문제입니다.
백트래킹을 설계하는 방법은 간단합니다.
1
이 적힌 칸마다1~5
크기의 색종이를 다 붙여보자.
지금까지 삼성 기출 문제를 풀어왔으면 이 정도는 충분히 구현하실 수 있을 겁니다.
3. 전체 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static final int SIZE = 10;
static final int MAX = 987654321;
static int CNT;
static int M[][] = new int [SIZE][SIZE];
static ArrayList<int[]> list = new ArrayList<>(); // 1이 적힌 칸의 좌표들
static int min(int depth, int[] paper) {
if (depth == CNT) {
// 하나라도 1이 있을 때 아주 큰 값을 리턴
for(int[] v : list)
if (M[v[0]][v[1]] == 1)
return MAX;
// 남아있는 1~5 색종이의 개수
int sum = 0;
for (int i = 1; i <= 5; i++) sum += paper[i];
// 사용한 색종이의 개수는 전체 개수(25)에서 sum을 빼면 됩니다.
return 25 - sum;
}
int ret = MAX;
int [] coord = list.get(depth);
int y = coord[0];
int x = coord[1];
// 이전 재귀의 cover 함수 호출로 0이 되었다면 다음 재귀로 계속 넘어갑니다.
if (M[y][x] == 0) return min(depth + 1, paper);
outer:
for (int size = 1; size <= 5; size++) {
// size 크기의 색종이를 다 사용했으면 넘어갑니다.
if (paper[size] <= 0) continue;
// 범위를 벗어나거나 0이 있는 칸이 있다면 루프를 빠져나옵니다.
for (int j = y; j < y + size; j++)
for (int k = x; k < x + size; k++)
if (j < 0 || j >= SIZE || k < 0 || k >= SIZE || M[j][k] == 0)
break outer;
// 백트래킹 영역
cover(y, x, size, 0); // (y, x)에서 size크기만큼 0으로 덮기
paper[size]--; // size 크기의 색종이 사용 횟수 차감
ret = Math.min(ret, min(depth + 1, paper)); // 다음 재귀 탐색
paper[size]++; // size 크기의 색종이 사용 횟수 복구
cover(y, x, size, 1); // (y, x)에서 size크기만큼 1로 복구
}
return ret;
}
// y, x 좌표에서 size만큼 color로 덮는 함수
static void cover(int y, int x, int size, int color) {
for (int i = y; i < y + size; i++)
for (int j = x; j < x + size; j++)
M[i][j] = color;
}
public static void main(String[] args) throws Exception {
for (int i = 0; i < SIZE; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < SIZE; j++) {
M[i][j] = Integer.parseInt(s[j]);
if (M[i][j] == 1)
list.add(new int[] {i, j});
}
}
CNT = list.size(); // 1이 적힌 칸의 개수
int ans = min(0, new int[] {0, 5, 5, 5, 5, 5}); // 1~5 사이즈 색종이의 초기 개수는 5개씩 있습니다.
bw.write((ans == MAX ? -1 : ans) + "");
bw.close();
}
}
Author And Source
이 문제에 관하여(색종이 붙이기 (17136)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-색종이-붙이기-17136저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)