[Gold / 17136] 색종이 붙이기

문제 링크

---

🔷 분류

브루트포스 알고리즘, 백트래킹

✒️ 문제 설명

<그림 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을 출력한다.

💻 코드 (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int P[10][10];
int S[6] = {0, 5, 5, 5, 5, 5};
int ans = 26;

bool check(int x, int y, int size) { // size 범위가 1인가?4
    if(x + size > 10 || y + size > 10) return false; // 종이 크기 넘어가면
	for(int i = x; i < x+size; i++) {
		for(int j = y; j < y+size; j++) {
			if(P[i][j] == 0) return false;
		}
	}
	return true;
}

void fill(int x, int y, int size, int num) { // size 만큼 num 으로 채우기
	for(int i = x; i < x+size; i++) {
		for(int j = y; j < y+size; j++) {
			P[i][j] = num;
		}
	}
}

void backtracking(int xy, int used) {
	if(xy == 100) { // break point 1 : 탐색 완료
		ans = min(used, ans);
		return;
	}
	if(ans <= used) return; // break point 2 : 최솟값 이상이면 종료
	int x = xy % 10;
	int y = xy / 10;
	
	// 현재 좌표 1이면
	if(P[x][y] == 1) {
		for(int i = 5; i >= 1; i--) {
			if(S[i] > 0 && check(x, y, i)) {
				S[i]--; // 종이 사용
				fill(x, y, i, 0); // 0으로 바꾸기
				backtracking(xy+1, used+1); // backtracking
				S[i]++; // 종이 채우기
				fill(x, y, i, 1); // 1로 바꾸기
			}
		}
	} else { // 현재 좌표 0이면
		backtracking(xy+1, used); // 다음 칸으로
	}
}	

	
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++) {
			cin >> P[i][j];
		}
	}
	backtracking(0, 0);
	if(ans == 26) cout << -1;
	else cout << ans;
	
	return 0;
}