[백준] #17136번 색종이 붙이기 (C++)

문제

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

10X10 종이 위에 1이 적힌 칸에 1~5 크기인 정사각형 색종이를 대입하여 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구하는 문제이다.
1~5 크기인 정사각형 색종이는 각 5개가 주어진다.
단, 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐서도 안된다.

접근 방식

문제를 보고 처음 생각한 방식은 가장 큰 색종이인 5x5 색종이부터 시작하여 차례대로 대입을 시도해서 색종이를 붙일 수 있는 최솟값을 찾아야 겠다고 생각했다.

하지만 금방 반례를 찾을 수 있었는데 아래와 같이 10X10 종이 위에 6X6 크기의 1로 채워진 정사각형이 있다고 생각해보면 5x5 색종이부터 붙이고 그냥 넘어간다면 대참사가 일어난다는 것을 알 수 있다.

즉, 모든 가짓수를 고려하는 완전탐색을 해나가되 최적화가 될 만한 부분을 찾는게 문제의 핵심이다.

풀이

먼저 모든 경우의 수를 전부 탐색해보기 위해 재귀 함수부터 작성하였다.

현재 칸에 1~5 정사각형의 크기인 색종이가 들어갈 수 있다면 색종이 크기만큼 종이에 0으로 칠하고 재귀함수를 호출하도록 구현하였다. (그럼 재귀 함수의 호출 개수가 곧 색종이를 붙일 수 있는 개수가 되므로 문제 풀기가 간단해진다)

재귀 함수의 기저조건에는 종이에 더 이상 색종이를 붙일 수 있는 칸이 없다면 현재까지 함수 호출의 개수가 최소가 되는지 확인하고 재귀를 종료시키도록 한다.

재귀 함수를 마치고나서는 다른 가짓수들을 탐색하기 위해 이전의 상태로 되돌아가는 작업 또한 작성한다. (재귀로 구현하는 조합 알고리즘과 같은 메커니즘)

그리고 함수 호출의 개수가 최소가 되는 값을 result라 했을 때, 재귀 함수 첫 단에 (지금까지의 함수 호출의 개수 > result)일 시 재귀를 종료시키는 조건문을 추가 시킨다면 가지치기가 가능해져 쓸모없는 연산을 방지할 수 있다.

코드

#include<iostream>

using namespace std;

int map[10][10];
int paper[5] = { 5, 5, 5, 5, 5 };
int result = 100;

bool check(int i, int k, int j) {
	for (int x = i; x <= i + j; x++) {
		for (int y = k; y <= k + j; y++) {

			if (map[x][y] == 0) {

				return false;
			}
		}
	}
	return true;
}

void fill(int i, int k, int j, int v) {
	for (int x = i; x <= i + j; x++) {
		for (int y = k; y <= k + j; y++) {
			map[x][y] = v;
		}
	}
}

bool fill_check() {
	for (int i = 0; i < 10; i++) {
		for (int k = 0; k < 10; k++) {
			if (map[i][k] == 1) return false;
		}
	}
	return true;
}

bool range_check(int x, int y) {
	if (x < 10 && y < 10) return true;
	return false;
}

void recur(int cnt) {	//cnt가 색종이를  붙이는 개수
	if (result < cnt) {	//기저 사례
		return;
	}

	if (fill_check()) {	//종이에 모두 0으로 되있을 시 true 반환
		if (result > cnt) result = cnt;	//최소값 저장
		return;
	}

	for (int i = 0; i < 10; i++) {
		for (int k = 0; k < 10; k++) {
			if (map[i][k] == 1) {
				for (int j = 4; j >= 0; j--) {	//색종이크기 j
					if (paper[j] > 0 && check(i, k, j) && range_check(i + j, k + j)) {
						paper[j]--;
						fill(i, k, j, 0);	//색종이가 들어갈 수 있다면 0으로 채우는거죠

						recur(cnt + 1);

						paper[j]++;
						fill(i, k, j, 1);

					}
				}
				return;
				//어차피 색종이를 다대입 시킨 후로는 더이상 반복문 돌 필요없음
			}
		}
	}
}

int main() {
	for (int i = 0; i < 10; i++) {
		for (int k = 0; k < 10; k++) {
			cin >> map[i][k];
		}
	}

	recur(0);	//색종이를 붙이는 갯수

	//함수 호출 개수 = 색종이를 붙이는 갯수

	cout << (result == 100 ? -1 : result);	
}

걸린 시간 : 1시간

현재 칸에 색종이가 들어갈 수 있는지 확인하는 함수에서 깜빡하고 범위 체크를 안해줘 색종이가 10X10 종이 바깥으로 벗어나는 일이 생겨 5번의 시도 끝에 통과할 수 있었다.