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

문제 : 색종이 붙이기

유형 : 완전탐색

문제 해석

• 색종이의 크기는 1x1, 2x2, 3x3, 4x4, 5x5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 있다.

• 색종이를 크기가 10x10인 종이 위에 붙인다.
  • 종이는 1x1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0또는 1이 적혀있다.

• 1이 적힌 칸만 모두 색종이로 덮여져야 한다.
  • 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안된다.
  • 0이 적힌 칸에는 색종이가 있으면 안 된다.

해결 전략

• 큰 색종이부터 종이에 붙일 수 있으면 붙인다.
  • 크기가 작은 색종이부터 붙일 경우
    • 1x1 색종이는 2x2, 3x3, 4x4, 5x5의 한 부분에 해당하는데, 2x2 색종이를 채워야 할 종이에 1x1 종이 4개를 채우는 상황은 절대 답이 될 수 없다.
  • 크기가 큰 색종이부터 붙일 경우
    • 위의 설명대로 큰 색종이를 붙여야 할 종이에 작은 색종이를 붙이는 상황은 답이 될 수 없다.
    • 큰 색종이 먼저 붙이면서 이전의 답 보다 현재 붙인 색종이가 더 많다면 바로 함수를 탈출하면 시간을 줄일 수 있다.
• 물론 완전 탐색 문제이므로 크기가 작은 색종이부터 붙여도 답은 맞다.

설계, 구현

• findPos() 함수를 통해 색종이를 붙일 좌표를 찾는다.
  • 좌표 값이 -1인 경우
    • 종이에 색종이를 모두 채워 넣은 것으로 지금까지의 색종이 최소 개수와 지금 필요한 색종이의 최소 개수를 비교한다.
  • 좌표값이 -1이 아닌 경우
    • 스티커를 붙일 종이가 있는 것으로 조건을 만족하는 스티커를 찾는다.
    • 각각의 스티커 중에 이미 5개를 붙였으면 붙이지 않는다.
    • isValidRange() 함수를 통해서 종이의 경계 밖으로 나가지 않았는지 검사한다. 종이의 경계 밖으로 나갔다면 조건을 충족하지 못한다.
    • isPossible() 함수를 통해서 색종이가 겹쳤는지, 0이 적힌 칸이 있는지를 검사한다. 색종이가 겹쳤거나, 0이 적혀 있다면 조건을 충족하지 못한다.
    • 모든 조건을 충족한다면 fill(y, x, type, 0) 함수를 통해서 적절한 타입의 색종이를 채워 넣고, 모든 종이를 색종이로 채웠거나, 채울 조건을 충족시키지 못했다면 다시 제자리로 돌아와 fill(y, x, type, 1) 함수를 통해서 채웠던 색종이를 다시 떼어낸다.

코드

#include <bits/stdc++.h>
#define MAX 10
#define INF 987654321
using namespace std;

int paper[11][11];
int sticker[6];
int answer = INF;

void init() {
	for (int i = 1; i <= MAX; i++) {
		for (int j = 1; j <= MAX; j++) {
			cin >> paper[i][j];
		}
	}
}

pair<int, int> findPos() {
	for (int i = 1; i <= MAX; i++) {
		for (int j = 1; j <= MAX; j++) {
			if(paper[i][j] == 1) return {i, j};
		}
	}
	
	return {-1, -1};
}

bool isValidRange(int y, int x, int type) {
	if(y + type > MAX + 1 || x + type > MAX + 1) return false;
	
	return true;
}

bool isPossible(int y, int x, int type) {
	for (int i = y; i < y + type; i++) {
		for (int j = x; j < x + type; j++) {
			if(paper[i][j] == 0) return false;
		}
	}
	
	return true;
}

void fill(int y, int x, int type, int state) {
	for (int i = y; i < y + type; i++) {
		for (int j = x; j < x + type; j++) {
			paper[i][j] = state;
		}
	}
}

void solve(int count) {
	if(count > answer) return;
	
	pair<int, int> pos = findPos();
	int y = pos.first;
	int x = pos.second;

	if(y == -1) {
		answer = min(answer, count);
		return;
	}
	
	for(int type = 5; type > 0; type--) {
		if(sticker[type] > 4) continue;
		if(!isValidRange(y, x, type)) continue;	
		if(!isPossible(y, x, type)) continue;

		fill(y, x, type, 0);
		sticker[type] += 1;
		solve(count + 1);	
		sticker[type] -= 1;
		fill(y, x, type, 1);	
	}
}

void getAnswer() {
	if(answer == INF) cout << -1;
	else cout << answer;
}

int main() {
	init();
	solve(0);
	getAnswer();
	return 0;
}