[BAEKJOON] 17136번 색종이 붙이기

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

 

문제조건

 

1.  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.
2. 각 종류마다 5개씩 가지고 있다.
3. 10×10인 종이에 색종이를 붙인다.
4. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다.
5. 필요한 색종이의 최소의 개수?
6. 모두 덮는것이 불가능한 경우 -1을 출력

 

접근방법

 

하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 방법또한 구현하기 너무 까다로웠고, 명확한 방법이 아닌것같았다.

그렇게 계속 생각만 한것같은데, 길이가 큰 것부터 접근하면 이 문제가 말끔히 해결되었다!

 

DFS로 brute force를 돌리고, 길이가 n일때 색종이를 붙일수 있을까에 대한 판단을 해주어 백트래킹으로 풀었다.붙일수 있다고 판단이 되면 그 칸은 붙인걸로 치고 다른 색종이를 붙이지 못하도록 0으로 바꿔줬다.종료조건으로는 종이를 모두 탐색했을때, 전부 0이면 색종이를 다 붙인 것이므로, 색종이를 붙이는 경우의 수 중 하나에 해당된다. 따라서 이 경우에 이때까지 저장된 가장 작은 값과 비교해서 더 작다면 갱신시켜줬다.

 

※ 모두 덮는것이 안되는 경우를 위해서 색종이의 갯수배열을 따로 두어, 이미 한종류의 색종이가 5개가 되었다면 진행하지 못하도록 해줬다.

 

소스코드

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

int map[11][11], res = 987654321;
int paper[6];

bool pos(int y, int x, int size) {
	for(int i = 0; i < size; i++)
		for (int j = 0; j < size; j++) 
			if (map[y + i][x + j] == 0) return false;
	return true;
}

void dfs(int cnt, int y, int x) {
	bool zero = true;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 1) {
				zero = false;
				y = i;
				x = j;
				break;
			}
		}
		if (zero == false) break;
	}
	//dfs탐색을 완료한 경우의 수일때 더 작은값으로 갱신
	if (zero) {
		res = min(res, cnt);
		return;
	}	
	if (cnt >= res) return;

	for (int i = 5; i >= 1; i--) {
		if (y + i > 10 || x + i > 10) continue;
		if (paper[i] >= 5) continue;
		if (pos(y, x, i)) {
			paper[i]++;
			for (int a = 0; a < i; a++)
				for (int b = 0; b < i; b++) map[y + a][x + b] = 0;
			dfs(cnt + 1, y, x);
			paper[i]--;
			for (int a = 0; a < i; a++)
				for (int b = 0; b < i; b++) map[y + a][x + b] = 1;
		}
	}
}


int main(){
	for (int i = 0; i < 10; i++) 
		for (int j = 0; j < 10; j++) cin >> map[i][j];
	dfs(0, 0, 0);
	if (res == 987654321) res = -1;
	cout << res;
}