백준 - 색종이 붙이기 (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();
	}
}