[백준/BOJ] 백준 17136번 : 색종이 붙이기

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

17136번: 색종이 붙이기

색종이를 붙여야 되는 자리를 발견하고, 발견한 자리를 1*1 색종이부터 5*5 색종이까지 붙여본다.

 

코드

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

int board[10][10];
int paper[6] = { 0,5,5,5,5,5 };

//n*n 색종이를 붙일수 있는지 확인
bool canStick(int x, int y, int n)
{
	if (paper[n] == 0) //n*n크기의 색종이가 없을때
		return false;

	if (x + n - 1 >= 10 || y + n - 1 >= 10) //크기를 넘어갔을때
		return false;

	for (int i = x; i < x + n; i++)
		for (int j = y; j < y + n; j++)
		{
			//해당 구역에 0이 있을때
			if (board[i][j] == 0)
				return false;
		}

	return true;
}

//n*n크기의 색종이를 붙인다
void Stick(int x, int y, int n)
{
	for (int i = x; i < x + n; i++)
		for (int j = y; j < y + n; j++)
			board[i][j] = 0;

	paper[n]--;
}

//n*n크기의 색종이를 뗀다
void Detach(int x, int y, int n)
{
	for (int i = x; i < x + n; i++)
		for (int j = y; j < y + n; j++)
			board[i][j] = 1;

	paper[n]++;
}

//1을 모두 덮었는지 확인
bool Check()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			if (board[i][j] == 1)
				return false;
		}

	return true;
}

int Solve()
{
	//1이 존재하지 않을때(1을 모두 덮었을때)
	//더 이상 색종이를 붙이지 않는다
	if (Check())
		return 0;

	int x, y;
	bool find_xy = false;
	int ret = 987654321;

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			//색종이를 붙여야 되는 자리를 발견했을때
			if (board[i][j] == 1)
			{
				x = i;
				y = j;

				find_xy = true; //색종이를 붙여야 되는 자리를 발견했다고 표시
				
				break;
			}
		}
		if (find_xy) //색종이를 붙여야 되는 자리를 발견했을때
			break;
	}

	for (int p = 1; p <= 5; p++) //1*1 색종이부터 5*5 색종이까지 붙여본다
	{
		//해당 색종이를 붙일수 있을때
		if (canStick(x, y, p))
		{
			Stick(x, y, p); //색종이 붙이기

			ret = min(ret, Solve() + 1);

			Detach(x, y, p); //색종이 떼기
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;
	int result;

	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			cin >> input;
			board[i][j] = input;
		}

	result = Solve();

	if (result == 987654321)
		cout << -1;
	else
		cout << result;

	return 0;
}