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

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

17136번: 색종이 붙이기

캐슬 디펜스와 같이 A형 기출문제였던 색종이 붙이기 문제!!

 

처음에는 그냥 로직을

맵을 돌면서 가장 큰 색종이부터 작아지는 순서대로 붙이는 그리디한 방식으로 짰다.

하지만 그렇게 하면 치명적인 오류가 있었다.

<잘못된 코드>

#include <cstdio>
#include <memory.h>
int map[11][11], paper[6] = { 0,5,5,5,5,5 }, cnt[6], ans=50;
bool c[11][11], check;
bool iscover(int s, int row, int col) {
	for(int i=0;i<s;i++)
		for (int j = 0; j < s; j++)
			if (!map[row + i][col + j]||c[row+i][col+j])return false;
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			c[row + i][col + j] = true;
	return true;
}
int main() {
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++) {
			scanf("%d", &map[i][j]);
			check |= map[i][j];
		}
	if (!check) {
		printf("0"); return 0;
	}
	for (int a = 1; a <= 5; a++) {
		int sum = 0; bool possible = true;
		for (int b = a; b >= 1; b--) {

			for (int i = 0; i < 10; i++)
				for (int j = 0; j < 10; j++)
					if (map[i][j]&&!c[i][j]) {
						check = iscover(b, i, j);
						if (check)cnt[b]++;
					}

			if (cnt[b] > 5) { possible = false; break; }
			sum += cnt[b];
		}

		if (possible && sum && sum < ans)ans = sum;
		memset(c, false, sizeof(c));
		memset(cnt, 0, sizeof(cnt));
	}
	printf("%d", ans == 50 ? -1 : ans);
	return 0;
}

 

이런 테이블이 존재한다고 가정해보자. 만약 5*5 색종이부터 4*4, 3*3, ... 이런식으로 붙인다면?

이런 형태가 우선적으로 만들어지겠지만, 남아있는 칸은 1*1 7장으로 채워야 하기 때문에 거를 수 있다.

위의 코드에서는 답이 12장으로 나오는데, 그 때 형태는 아래와 같다.

하지만 처참하게 틀렸다. 그리디하게 풀면 안 되고 특정 색종이를 붙였다고 가정할 때, 안 붙였다고 가정할 때를 이용한 백트래킹(완전탐색)을 이용해줘야 했다. 그래서 위의 그림은 아래와 같은 형태가 정답이다.

기억하자. 삼성 역량테스트&코딩테스트는 완전탐색, 구현, BFS라는 걸.....

 

그래서 테이블의 행과 열을 인자로 하는 백트래킹 함수를 만들어, 특정 색종이를 붙일지or안 붙일지를 고려해주는 백트래킹 방식으로 다시 구현했다.

#include <cstdio>
#include <memory.h>
int map[25][25], cnt, paper[6], ans = 50;
bool cvr[11][11], check;
bool iscover(int s, int row, int col) {
	if (row + s > 10 || col + s > 10)return false;
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			if (!map[row + i][col + j] || cvr[row + i][col + j])return false;
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			cvr[row + i][col + j] = true;
	return true;
}
void recover(int s, int row, int col) {
	for (int i = 0; i < s; i++)
		for (int j = 0; j < s; j++)
			cvr[row + i][col + j] = false;
}
void func(int r, int c, int s) {
	for (int i = 1; i <= 5; i++)
		if (paper[i] > 5)return;

	if (c >= 10) { 
		func(r + 1, 0, s); return; 
	}
	if (r >= 10||s==cnt) { 
		int sum = 0;
		for (int i = 1; i <= 5; i++)sum += paper[i];
		if (sum < ans)ans = sum;
		return; 
	}

	if (!map[r][c] || cvr[r][c]) {
		func(r, c + 1, s);
		return;
	}

	for (int i = 5; i > 0; i--) {
		check = iscover(i, r, c);
		if (check) {
			paper[i]++;

			func(r, c + i, s+i*i);

			paper[i]--;
			recover(i, r, c);
		}
	}
	return;
}
int main() {
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++) {
			scanf("%d", &map[i][j]);
			check |= map[i][j];
			cnt += map[i][j];
		}
	if (!check) {
		printf("0"); return 0;
	}
	func(0,0,0);
	printf("%d", ans == 50 ? -1 : ans);
	return 0;
}