[백준 17136] 색종이 붙히기

분류 

dfs, 구현

요구사항

색종이를 최소로 이용하여 map에 있는 1을 다 가릴 수 있도록 하기

풀이

문제의 전체 흐름은

1. 현재 위치에서 붙일 수 있는 색종이 다 붙여보기

1.1. 붙이고 dfs로 이동

1.2 종료 후, 다시 복구하기

2. 다음 위치로 이동

3. 종료 조건 명시 하기

 

문제의 핵심은 현재에서 할 수 있는 행동을 모두 취한 뒤, 그 다음 위치로 이동하는 것이다.

현재 위치를 다시 한번 탐색할 경우, 탐색의 깊이가 깊어진다

 

#include <iostream>
#include <algorithm>

using namespace std;
int map[10][10];
int ansflag = 0;
int ans = 987654321;
int visit[6] = { 0,5,5,5,5,5 };
bool check(int r, int c, int num) {
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			if (i < 0 || j < 0 || i >= 10 || j >= 10) return false;
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}
void erase(int r, int c, int num) {
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			map[i][j] = 0;
		}
	}
}
void recover(int r, int c, int num) {
	for (int i = r; i < r + num; i++) {
		for (int j = c; j < c + num; j++) {
			map[i][j] = 1;
		}
	}
}
bool anscheck() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 1) return false;
		}
	}
	return true;
}

void solve(int r, int c, int cnt) {
	//cout << "R" << r << "C" << c << endl;
	if (cnt > ans) return;
	if (anscheck()) {
		//	cout << "A" << endl;
		ansflag = 1;
		ans = min(ans, cnt);
		return;
	}
	if (r == 10) return;
	if (c >= 10) {
		solve(r + 1, 0, cnt);
		return;
	}
	if (map[r][c] == 0) {
		solve(r, c + 1, cnt);
		return;
	}

	//지금 할 수 있는 행동 1~5까지 검사하고 더 들어가기
	for (int k = 5; k >= 1; k--) {
		if (check(r, c, k)) {
			if (visit[k] - 1 < 0) continue;
			visit[k]--;
			erase(r, c, k);
			solve(r, c + k, cnt + 1);
			visit[k]++;
			recover(r, c, k);
		}
	}
}
int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	solve(0, 0, 0);
	if (ansflag == 1) {
		cout << ans << endl;
	}
	else {
		cout << -1 << endl;
	}
}