[백준] 17136 - 색종이 붙이기

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

17136번: 색종이 붙이기

 

이 문제는 10 * 10 크기의 종이가 고정되어 있다는 걸로 보아 완전 탐색(+ 백트래킹)의 느낌이 났다.

 

처음에는 만약 1을 발견한다면 항상 가능한 큰 종이부터 붙이게끔 그리디 하게 풀었다.

하지만, 만약 8 * 8 크기의 1을 그리디 하게 붙이면 5 * 5 1장, 3 * 3 2장, 2 * 2 2장, 1 * 1 5장 총 10장을 사용하지만,

최선의 방법은 4 * 4를 4장 붙이는 것이다.

따라서 모든 경우의 수를 다 해보아야 한다.

 

1. x좌표를 1부터 10까지, y좌표를 1부터 10까지 모두 탐색하며 1을 찾는다.
2. 색종이를 붙일 수 있는지 판단한 후,
3. 붙일 수 있다면 붙이고 색종이의 수를 갱신시켜준 후 다음 탐색을 한다.

이때 어떤 순서로 색종이를 붙어야 하는지 확실하지 않으므로 백트래킹 기법을 이용해 모든 경우의 수를 다 써본다.

 

#include <iostream>
using namespace std;

int map[10][10], p[6] = { 0,5,5,5,5,5 };
int ans = -1;

void go(int x, int y, int cnt) {
	if (ans != -1 && ans < cnt) return;

	if (x == 10) {
		if (ans == -1 || ans > cnt) {
			ans = cnt;
		}
		return;
	}
	
	if (y == 10) {
		go(x + 1, 0, cnt);
		return;
	}

	if (map[x][y] == 0) {
		go(x, y + 1, cnt);
		return;
	}

	for (int s = 1; s <= 5; s++) {
		if (x + s > 10 || y + s > 10 || p[s] == 0)continue;

		bool ok = true;
		for (int i = x; i < x + s; i++) {
			for (int j = y; j < y + s; j++) {
				if (map[i][j] != 1) {
					ok = false;
					break;
				}
			}
			if (!ok)break;
		}
		if (!ok)continue;

		for (int i = x; i < x + s; i++) {
			for (int j = y; j < y + s; j++) {
				map[i][j] = 0;
			}
		}
		p[s]--;
		go(x, y + s, cnt + 1);
		p[s]++;
		for (int i = x; i < x + s; i++) {
			for (int j = y; j < y + s; j++) {
				map[i][j] = 1;
			}
		}
	}
}

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

	cout << ans;
}