#17136. 색종이 붙이기

Problem

• 문제링크

Solution

• DFS + BackTracking을 사용하여 푼다.
  (처음에 BFS+Greedy를 이용해 풀었다가 틀렸다…반례가 존재)
• 10 x 10 크기의 모든 배열에서 모든 지점을 탐색한다.
  • 탐색 횟수가 100이라면 모든 지점을 탐색한 경우라 값을 갱신하고 종료한다.
  • 행과 열은 0 → 100개의 원소들에 맞게 계산
  • 이미 ans 가 지금까지 구한 개수(cnt) 보다 크면 종료 (BackTracking)
  • 해당 지점이 1이면 색종이 크기가 큰 5부터 검사 시작
    • 해당 크기가 가능하면 붙이고 다음 경우 탐색
      탐색이 끝난 경우 원래대로 돌려놓아야 모든 경우 탐색이 가능하다.
  • 해당 지점이 0이면 다음 번째 원소 탐색

1 Try

#include <iostream>
using namespace std;
int ans = 100;
int map[10][10];
int type[5] = {5, 5, 5, 5, 5 }; // 1 2 3 4 5 종류
void Update(int x, int y, int size, int status) {
	for (int i = x; i < x + size; ++i) {
		for (int j = y; j < y + size; ++j) {
			map[i][j] = status;
		}
	}
}
bool Check(int x, int y, int size) {
	if (x + size > 10 || y + size > 10) return false; // 범위 밖
	for (int i = x; i < x + size; ++i) {
		for (int j = y; j < y + size; ++j) {
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}
void DFS(int n, int cnt) {
	if (n == 100) { // 모든 경우를 탐색한 경우 (총 100개)
		if (ans > cnt) ans = cnt;
		return;
	}
	int x = n / 10;
	int y = n % 10;
	if (ans <= cnt) return; // BackTracking

	if (map[x][y] == 1) {
		for (int i = 5; i > 0; --i) { // 크기 5부터 시작
			if (type[i-1] > 0) {
				if (Check(x, y, i)) {
					type[i - 1]--;
					Update(x, y, i, 0); // 색종이 붙이기
					DFS(n+1, cnt + 1);
					Update(x, y, i, 1); // 색종이 다시 때기
					type[i - 1]++;
				}
			}
		}
	}
	else DFS(n + 1, cnt);
}
int main() {
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> map[i][j];
		}
	}
	DFS(0, 0);
	if (ans == 100) ans = -1;
	cout << ans << "\n";
	return 0;
}