(c++)백준 17136번: 색종이 붙이기

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

[풀이]

dfs를 이용하여 백트래킹을 하였다.

1. 종이에서 1 찾기: 1 없으면 지금까지 붙여왔던 종이 개수와 최솟값 비교하여 갱신

2. 1이 있는 칸에 1*1, 2*2, 3*3, 4*4, 5*5 종이를 붙일 수 있는지 확인(종이 붙이는 범위 안에 0이 있으면 안 됨)

3. 종이를 붙이고 붙인 종이 개수에 +1하여 재귀

4. 붙인 종이 떼기

 

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 10;
int Min = 987654321;
int Map[Max][Max];
int paper[] = { 0,0,0,0,0, };//1,2,3,4,5쓰인 개수

bool can_attach(int x, int y, int s) {
	for (int i = 0; i <= s; i++) {
		for (int j = 0; j <= s; j++) {
			if (Map[x + i][y + j] == 0)
				return false;
		}
	}
	return true;
}

void update_Map(int x, int y, int s, int attached) {
	for (int i = 0; i <= s; i++) {
		for (int j = 0; j <= s; j++) {
			Map[x + i][y + j] = attached;
		}
	}
}

void dfs(int x, int y, int paper_cnt) {
	//1찾기
	while (Map[x][y] == 0) {
		if (++y >= 10) {
			if (++x >= 10) {
				Min = min(Min, paper_cnt);
				return;
			}
			y = 0;
		}
	}
	//현재까지의 최솟값 보다 크면 가지치기
	if (Min <= paper_cnt)
		return;
	//모든 종이에 대해
	for (int i = 4; i >= 0; i--) {
		//범위 벗어나거나 해당 종이 5장 다 썼을 경우
		if (x + i >= Max || y + i >= Max || paper[i] == 5)
			continue;
		//붙일 수 있으면(해당 영역이 모두 1이면)
		if (can_attach(x, y, i)) {
			paper[i]++;
			update_Map(x, y, i, 0);
			dfs(x, y, paper_cnt + 1);
			paper[i]--;
			update_Map(x, y, i, 1);
		}
	}
}

void solution() {
	int total_one = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 1)
				total_one++;
		}
	}
	if (total_one == 0) {
		cout << 0 << '\n';
		return;
	}
	else if(total_one == Max * Max) {
		cout << 4 << '\n';
		return;
	}
	dfs(0, 0, 0);
	if (Min == 987654321)
		cout << -1 << '\n';
	else
		cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solution();
	return 0;
}