[BOJ 17136 // C++] 색종이 붙이기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17136번 문제인 색종이 붙이기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/17136 

17136번: 색종이 붙이기

각 칸을 행 오름차순으로, 같은 행이라면 열 오름차순으로 둘러보면서 1을 만날 때마다 그 칸을 채우기 위해 색종이를 붙이려고 시도하는 모든 (색종이를 붙이는 순서에 대한) 순열의 경우를 시도해보며 문제를 해결하자.

 

이와 같은 순열의 경우의 수는 생각보다 많지는 않다는 점을 관찰하자. 예를 들어 한변의 길이가 4인 색종이와 5인 색종이는 두 종류를 합쳐서 최대 네 장까지밖에 붙이지 못하는 등 가능한 조합의 종류에는 많은 제약이 따름을 관찰하자.

 

아래의 구현과 같이 가장 아래쪽과 오른쪽에 0으로 가득 찬 가상의 행과 열을 하나씩 추가해주면 구현을 편리하게 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[11][11];

int paper[6];
int papercnt = 0;
int mn = 1000000007;

void func(int r, int c) {
	if (r == 10) {
		mn = min(mn, papercnt);
		return;
	}

	int nxtr = r, nxtc = c + 1;
	if (nxtc == 10) nxtr++, nxtc = 0;

	if (arr[r][c] == 0) func(nxtr, nxtc);
	else {
		papercnt++;
		for (int k = 1; k < 6; k++) {
			bool chk = 1;
			for (int rr = 0; rr < k; rr++) {
				for (int cc = 0; cc < k; cc++) {
					if (arr[r + rr][c + cc] == 0) chk = 0;
				}
			}
			if (chk == 0) break;
			if (paper[k] == 0) continue;
			paper[k]--;
			for (int rr = 0; rr < k; rr++) {
				for (int cc = 0; cc < k; cc++) {
					arr[r + rr][c + cc] = 0;
				}
			}
			func(nxtr, nxtc);
			for (int rr = 0; rr < k; rr++) {
				for (int cc = 0; cc < k; cc++) {
					arr[r + rr][c + cc] = 1;
				}
			}
			paper[k]++;
		}
		papercnt--;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	paper[1] = paper[2] = paper[3] = paper[4] = paper[5] = 5;

	for (int r = 0; r < 10; r++) {
		for (int c = 0; c < 10; c++) {
			cin >> arr[r][c];
		}
	}

	func(0, 0);

	if (mn == 1000000007) cout << -1;
	else cout << mn;
}