[BOJ] 17136. 색종이 붙이기

문제 원본 : https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int map[10][10];
vector<pair<int, int>> v;
int blk_cnt[5] = { 5,5,5,5,5 };
int cnt;
int ans;
bool succ;

bool possible(int r, int c, int n)
{
	if (r + n > 10 || c + n > 10) return false;

	for (int i = r; i < r + n; i++)
		for (int j = c; j < c + n; j++)
			if (map[i][j] != 1)
				return false;
	return true;
}

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

void useBlock(int r, int c, int n)
{
	for (int i = r; i < r + n; i++)
		for (int j = c; j < c + n; j++)
			map[i][j] = n + 1;
}

void go(int r, int c)
{
	int back_map[10][10];
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			back_map[i][j] = map[i][j];

	int size = v.size();
	for (int i = 5; i >= 1; i--)
	{
		if (possible(r, c, i) && blk_cnt[i - 1])
		{
			blk_cnt[i - 1]--;
			cnt++;
			if (cnt > ans)
			{
				cnt--;
				blk_cnt[i - 1]++;
				return;
			}
			useBlock(r, c, i);

			if (clear())
			{
				ans = min(cnt, ans);
				succ = true;
			}
			for (int i = 0; i < size; i++)
			{
				if (map[v[i].first][v[i].second] == 1)
				{
					go(v[i].first, v[i].second);
					break;
				}
			}
			cnt--;
			blk_cnt[i - 1]++;
			for (int i = 0; i < 10; i++)
				for (int j = 0; j < 10; j++)
					map[i][j] = back_map[i][j];
		}
	}
}


int main()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			cin >> map[i][j];
			if (map[i][j])
				v.push_back(make_pair(i, j));
		}

	ans = 1234567890;

	if (v.size() == 0)
	{
		printf("0\n");
		return 0;
	}
	go(v[0].first, v[0].second);
	succ ? printf("%d\n", ans) : printf("-1\n");
}

• 큰 종이부터 붙여가면서 안 되는 경우를 가지치기하는 방식으로 해결.
• 백트래킹은 아직도 어렵다.