백준 17136: 색종이 붙이기

문제 요약

색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

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

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

문제 분류

• 브루트포스 알고리즘
• 백트래킹

문제 풀이

언뜻보면 그리디하게 풀 수 있을것 같지만, 색종이의 개수가 제한되어있기 때문에 전혀 안된다.

즉, 사이즈를 1~5까지 전부 대보면서 DFS탐색하면 된다. 우선 현재까지 답을얻은 색종이의 최소 개수를 전역변수로 두고, 탐색중에 사용하고 있는 색종이의 개수가 이 최소 개수보다 많거나 같게 된다면 탐색을 바로 종료하면 된다.

탐색 자체도 어렵지 않은데, 이미 방문하였거나 탐색중인 곳이 0이라면 다음칸으로 옮겨 탐색한다.

만약 1일 경우에는 사이즈를 1부터 5까지 유효한지 확인해본다. 유효하다면 색종이를 사용하고, 다음 DFS를 수행한 후에, 다시 색종이를 떼주면 된다.

코드적으로 설명하자면 size를 1부터 5까지 반복하여 유효한지 검사해본다. size크기의 색종이가 이미 5번 이상 사용되었거나, 범위가 유효하지 않으면 false이다. 현재 위치로부터 size크기만큼 범위의 원소 중 방문한 원소가 있거나 0이 있어도 false이다. 모든 조건을 통과했다면 true를 반환한다.

즉, '현재위치에 size크기의 색종이를 사용한다' = '현재위치로부터 size크기만큼 visited배열을 true로 설정한다'이고, '그 색종이를 뗀다' = '현재위치로부터 size크기만큼 visited배열을 false로 설정한다'가 된다.

그렇게 마지막 인덱스에 다다르면, 마지막 원소와 방문여부도 검사하여 계산에 넣고, 성공했다는 뜻의 전역변수 res를 true로 설정한다. res는 기본 false로, 색종이를 사용할수 없는 경우일때 -1를 출력하는 플래그로 사용한다.

가령 사이즈가 3인 색종이를 사용할 수 없다고 해도 4,5인 색종이를 사용할 수 있으므로 조건문에 주의하자. 마지막 원소가 1일때 색종이를 사용할 때에도 색종이를 사용한 것이므로, 유효한지 그 개수를 검사해 보아야 한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int ary[10][10];
bool visited[10][10], res = false;
int pcnt[5], cnt = 26;

bool valid(int idx, int size) {
	int y = idx / 10, x = idx % 10;
	if (x + size > 10 || y + size > 10) return false;
	if (pcnt[size - 1] >= 5) return false;
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			if (ary[i][j] == 0 || visited[i][j]) return false;
	return true;
}

void usePaper(int idx, int size) {
	int y = idx / 10, x = idx % 10;
	pcnt[size - 1]++;
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			visited[i][j] = true;
}

void unusedPaper(int idx, int size) {
	int y = idx / 10, x = idx % 10;
	pcnt[size - 1]--;
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			visited[i][j] = false;
}

void dfs(int idx, int fcnt) {
	int y = idx / 10, x = idx % 10;
	if (fcnt >= cnt) return;
	if (idx == 99) {
		if (!visited[y][x] && ary[y][x] == 1) {
			if (valid(idx, 1)) fcnt++;
			else return;
		}
		if (cnt > fcnt) cnt = fcnt;
		res = true;
		return;
	}
	if (visited[y][x] || ary[y][x] == 0) dfs(idx + 1, fcnt);

	for (int size = 1; size <= 5; size++) {
		if (valid(idx, size)) {
			usePaper(idx, size);
			dfs(idx + 1, fcnt + 1);
			unusedPaper(idx, size);
		}
    }
}

int main()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			scanf("%d", &ary[i][j]);
	dfs(0, 0);
	if (res) printf("%d", cnt);
	else printf("-1");

	return 0;
}