BOJ 17136 - 색종이 붙이기

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

접근

접근은 어렵지 않다. 그냥 모든 칸에 색종이를 붙여보면 된다.
백트래킹 방식으로 유망하지 않은 부분에서는 return을 붙여주면서, 브루트포스로 구하면 된다.
구현하는 것이 풀이 방식에 따라 코드 길이가 천차만별일 것 같다.

풀이

처음엔 vector<vector>를 함수 인자로 갖고 다닐까 생각했는데,
굳이 그럴 필요가 없을 것 같아 전역으로 선언했다.

remain을 parameter로 둬서 탈출문에 적용시켰다.
y, x 값에 대한 전처리도 간단하게 해주면 된다.

크기를 1 ~ 5까지 확인하면서, 색종이가 있으면 붙여준다.
재귀에 들어가기 전 값을 바꿔주고, 나올 때 값을 다시 바꿔주는 작업만 잘 수행하면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int answer = 30, paper[5] = { 5, 5, 5, 5, 5 };
vector<vector<int>> arr(10);

int use_paper()
{
	int ret = 25;
	FUP(i, 0, 4) ret -= paper[i];
	return ret;
}

void change(int y, int x, int len)
{
	FUP(i, y, y + len)
	{
		FUP(j, x, x + len)
		{
			arr[i][j] ^= 1;
		}
	}
}

void solve(int y, int x, int remain)
{
	if (remain == 0)
	{
		answer = min(answer, use_paper());
		return;
	}
	if (x >= 10)
	{
		solve(y + 1, 0, remain);
		return;
	}
	if (!arr[y][x]) solve(y, x + 1, remain);
	FUP(len, 0, 4)
	{
		if (x + len >= 10 || y + len >= 10) break;
		bool ok = true;
		FUP(i, y, y + len)
		{
			if (!arr[i][x + len]) ok = false;
		}
		FUP(j, x, x + len)
		{
			if (!arr[y + len][j]) ok = false;
		}
		if (!ok) break;
		if (!paper[len]) continue;
		change(y, x, len);
		paper[len]--;
		solve(y, x + len + 1, remain - (len + 1) * (len + 1));
		paper[len]++;
		change(y, x, len);
	}
}

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

	int remain = 0;
	FUP(i, 0, 9)
	{
		arr[i].resize(10);
		FUP(j, 0, 9)
		{
			CIN(arr[i][j]);
			remain += arr[i][j];
		}
	}
	solve(0, 0, remain);
	answer == 30 ? COUT(-1) : COUT(answer);

	return 0;
}