[BOJ] 17136 - 색종이 붙이기

문제 링크

스포를 당해서 쉽게 풀었던 문제다.
어줍짢게 시간복잡도를 줄인다고 최선의 경우의 수를 찾아 그리디하게 접근하면 틀리는 문제(라고 한다. 그렇게 들어서 그리디하지 않은 방법으로만 시도했다.)
일단 현재 시점에서 붙일 수 있는 모든 경우의 수를 시도해주었다.

소스코드

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

int paper[15][15], color[6], ans = 99;

bool is_in_range(int x, int y) {
	return x >= 0 && x < 10 && y >= 0 && y < 10;
}

bool is_attachable(int x, int y, int size) {
	if (color[size] >= 5) return false;
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			if (!paper[x + i][y + j])
				return false;
	return true;
}

void attach(int x, int y, int size) {
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			paper[x + i][y + j] = 0;
}

void remove(int x, int y, int size) {
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			paper[x + i][y + j] = 1;
}

void go(int x, int y, int count) {
	for (int i = 1; i <= 5; i++) {
		if (!is_in_range(x + i - 1, y + i - 1) || !is_attachable(x, y, i))
			continue;
		attach(x, y, i);
		color[i]++;
		bool ck = true;
		for (int r = x; ck && r < 10; r++)
			for (int c = 0; ck && c < 10; c++)
				if (paper[r][c]) {
					ck = false;
					go(r, c, count + 1);
				}

		if (ck) ans = min(ans, count + 1);
		remove(x, y, i);
		color[i]--;
	}
}

int main(void) {
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			scanf("%d", paper[i] + j);

	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			if (paper[i][j]) {
				go(i, j, 0);
				printf("%d", ans == 99 ? -1 : ans);
				return 0;
			}

	printf("%d", 0);
	return 0;
}