[ 백준-17136번 / 완전탐색 / 백트레킹 ] 색종이 붙이기

1. 문제

---

 

17136번: 색종이 붙이기

문제

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

<그림 1>

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

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

입력

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

출력

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

예제 입력 1 복사

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

0

예제 입력 2 복사

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 2 복사

4

 

 

 

 

 

2. 소스코드

---

1회차

 

- 일반적인 DFS로 푼다면 백트래킹 없이 절대로 풀 수 없는 문제. 그런데 백트래킹을 어떻게 할지 몰라 풀지 못하였음.

- 다른 사람의 소스코드를 참조함. 백트래킹 아이디어는 1~5번 색종이를 모두 붙일 수 없는 칸이 존재하면 return.

- 기존엔 1~5번 종이를 먼저 정하고 N x N 칸을 순회 했는데, 이러면 위의 백트래킹 아이디어를 사용할 수 없음. 

- 수행시간이 30ms로 상위권 8ms에 비해 느림. 

- 백트래킹 조건에 대해 더 생각해 볼 것.

 

#include <cstdio>
using namespace std;

/*
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0
*/

const int pSize = 10;
int cnt[5], ans = 1000;

struct Info{
	int map[pSize][pSize];
	int area, res;
}info;

void dfs(Info info, int prevX, int prevY) {
	
	Info temp = info;
 
	if (temp.area == 0 ) {
		if (ans > temp.res) 
			ans = temp.res;
		return;
	}
	bool out = false;
	for (int i = prevX; i < pSize; ++i) {
		for (int j = prevY; j < pSize; ++j) {
			if (temp.map[i][j])  { 
				for (int pNum = 4; pNum >= 0; --pNum) {
					//(pNum+1)칸 스티커를 붙일 수 있는가?
					bool isCanAttach = out = true;
					if (i + pNum  >= pSize or j + pNum >= pSize) continue;
					//해당칸에 색종이를 붙일 수 있는 가?
					for (int n = i; n < i + (pNum + 1); ++n) {
						for (int m = j; m < j + (pNum + 1); ++m) {
							if (temp.map[n][m] != 1) {
								isCanAttach = false; break;
							}
						}
						if (!isCanAttach) break;
					}
					//붙일 수 있으면 붙인다.
					if (isCanAttach and cnt[pNum] < 5) {
						for (int n = i; n < i + (pNum + 1); ++n) { 
							for (int m = j; m < j + (pNum + 1); ++m) {
								temp.map[n][m] = 0;
							}
						}
						temp.area -= (pNum + 1) * (pNum + 1);
						++cnt[pNum]; ++temp.res;
  
						dfs(temp, i, j);
 
						temp.area += (pNum + 1) * (pNum + 1);
						--cnt[pNum]; --temp.res;
 
						for (int n = i; n < i + (pNum + 1); ++n) { 
							for (int m = j; m < j + (pNum + 1); ++m) {
								temp.map[n][m] = 1;
							}
						}
					}				 
				}//end for m
			}//end if
			if (out) break;
		}//end for j
		prevY = 0;
		if (out) break;
	}
	return;
}

int main() {
	for (int i = 0; i < pSize; ++i) {
		for (int j = 0; j < pSize; ++j) {
			scanf("%d", &info.map[i][j]);
			if (info.map[i][j]) ++info.area;
		}
	}
	dfs(info, 0 , 0);

	if (ans == 1000) printf("-1");
	else printf("%d", ans);

	return 0;
}