[백준]17136 색종이 붙이기 - C/C++

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

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

---

재귀의 방식으로 1을 발견했을 때 붙일 수 있는 색종이를 붙여보고 붙인 경우와 붙일 수 있지만 안 붙인 경우로 나누어 문제를 풀면 된다.

문제가 색종이의 최소 개수를 구하는 것이기 때문에 무조건 큰 색종이를 붙이는 것보다 붙일 수 있지만 안 붙인 경우가 더 좋을 수 있다. 그러므로 1을 찾은 다음 붙일 수 있는 색종이를 붙여 보고 붙인 경우를 재귀 형식으로 확인해보고 다시 함수로 돌아왔을 때 색종이를 제거하고 다음 경우를 확인하면 된다. 재귀 함수의 종료 조건은 전체 종이의 마지막인 mat [9][9]에 도달했을 때이다.

 

여기서 조심해야 할 점은 i+s > 10 || j + s > 10에서 등호가 없는 이유는 j+s 가 10이 되면 인덱스를 벗어난다고 생각할 수 있지만 i, j에 붙이는 것이기 때문에 1을 빼주어야 한다. 예를 들어 i, j 가 둘 다 9 여도 사이즈 s=1의 색종이를 [9][9]에 붙일 수 있다. 

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

int mat[11][11];
int paper[6] = { 0 };
int min_cnt= 987654321;
int check(int x,int y,int k) {
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			if (!mat[x+i][y+j])
				return 0;
		}
	}
	return 1;
}

void change(int x, int y, int k,int to) {
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			mat[x+i][y+j] = to;
		}
	}
}
void dfs(int i,int j, int p_cnt) {
	while (!mat[i][j]) {
		if (j++ >= 10) {
			if (i++ >= 10) {
				min_cnt = min(min_cnt, p_cnt);
				return;
			}
			j = 0;
		}
	}
	if (min_cnt <= p_cnt) return;
	for (int s = 5; s >= 1; s--) {
		if (paper[s] == 5 || i + s > 10 || j + s > 10) continue;
		if (check(i, j, s)) {
			change(i, j, s, 0);
			paper[s]++;
			dfs(i, j, p_cnt + 1);
			change(i, j, s, 1);
			paper[s]--;
		}
	}
	return;
}

int main () {
	for (int i = 0; i < 10; i++) 
		for (int j = 0; j < 10; j++)
			cin >> mat[i][j];
	dfs(0,0,0);
	if (min_cnt == 987654321) cout << -1;
	else cout << min_cnt;
}

---

이 문제 역시 친구가 고전을 하고 있길래 같이 푼 문제다. 재귀를 활용하면 사이즈가 너무 커질까 봐 일단 사용하지 않고 문제를 풀었다. 그랬더니 예제는 다 맞았지만 21%에서 틀렸습니다가 나왔다. 반례를 찾아보니 꼭 5*5를 붙일 수 있다고 붙이는 것이 최선이 아니란 것을 알게 되었고 붙이는 경우와 안 붙이는 경우를 모두 확인해봐야 한다면 재귀를 활용할 수밖에 없을 것이라고 판단했다. 그래서 재귀를 사용하여 풀어보니 맞게 되었다. 배열의 사이즈가 10*10밖에 되지 않기 때문에 시간이 그렇게 많이 걸리지는 않는 것 같다!