[DFS 백트래킹] 백준 17136 색종이 붙이기 C++

 

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

17136번: 색종이 붙이기

 

#include <iostream>
#include <cstring>
#include <limits.h>

using namespace std;

int ans = INT_MAX;
int paper[10][10];
int cnt[5] = { 5,5,5,5,5 };

bool check(int x, int y, int idx) {
	if (((x + idx) > 10) || ((y + idx) > 10)) return false;
	for (int i = y; i < y + idx; i++) {
		for (int j = x; j < x + idx; j++) {
			if (paper[i][j] == 0) return false;
		}
	}
	return true;
}

void make(int x, int y, int idx, int val) {
	for (int i = y; i < y + idx; i++) {
		for (int j = x; j < x + idx; j++) paper[i][j] = val;
	}
}

void dfs(int x, int y, int depth) {
	if (y == 10) return; // y만 리턴
	if (x == 10) x = 0;

	int newx = -1, newy = -1;
	for (int i = y; i < 10; i++) { // for문 위치 조심(dfs 안에 for문 필요-색종이 상태 다 다름)
		for (int j = x; j < 10; j++) {
			if (paper[i][j] == 0) continue;
			else {
				newx = j; newy = i; // 새 변수 만들기
				break;
			}
		}
		if (newx != -1) break;
		x = 0;
	}

	if (ans <= depth) return; // 시간 단축
	if (newx == -1) { // 종료 조건 조심
		ans = min(ans, depth);
		return;
	}

	for (int k = 5; k > 0; k--) {
		if (cnt[k - 1] == 0) continue; // return 아님
		if (check(newx, newy, k) == true) {
			// 색종이 상태 바꾸기
			make(newx, newy, k, 0);
			cnt[k - 1]--; // k(X), k-1(O)
			dfs(newx + k, newy, depth + 1);
			make(newx, newy, k, 1);
			cnt[k - 1]++;
		}
	}
}

int main() {
	memset(paper, 0, sizeof(paper));

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) cin >> paper[i][j];
	}

	dfs(0, 0, 0);

	if (ans == INT_MAX) ans = -1;
	cout << ans;

	return 0;
}