[백준] 색종이 붙이기 (17136번)

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1 복사

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

0

---

주어진 종이 위에 최소한의 수로 색종이를 붙이는 문제이다.

색종이는 겹치거나 종이를 벗어날 수 없고, 이미 0인 곳에 색종이를 덧대면 안된다.

 

문제는 dfs를 이용해서 해결했다.

보통 문제에 비해 함수가 많이 사용됐다.

모두 0인지 확인하는 함수, 0이나 1로 채우는 함수, 다음으로 채워야 할 지점을 구하는 함수, 색종이를 채울 수 있는 지 확인하는 함수가 쓰였다.

 

dfs는 사용한 색종이 수를 매개변수로 받아 넘긴다.

모두 0으로 채워져있으면 최소값을 최신화한 후 종료한다.

채울 곳이 남았다면 다음으로 채워야 할 지점을 찾는다. 

색종이는 제일 좌측 상단부터 채운다.

 

채울 지점을 찾았으면 그 위치에서 크기가 5인 색종이부터 채울 수 있는지 확인한다. 즉 색종이의 크기만큼 모두 1로 채워져있는지 확인한다. 채울 수 있다면 해당 크기의 색종이 개수를 줄인 후, 0으로 채우고 dfs에 색종이 수를 +1 해서 넘긴다. 

dfs를 마치고 오면 다시 종이를 0으로 채우고 해당 크기의 색종이 수를 늘린다. 

 

문제를 보면 어려워 보이고 어찌할 지 모르겠지만 dfs로 해결할 수 있다는 힌트를 얻으면 구현은 크게 어렵지 않다.

 

 

 

코드 원본 :  https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%83%89%EC%A2%85%EC%9D%B4%20%EB%B6%99%EC%9D%B4%EA%B8%B0%20(17136%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int p[11][11];
int paper[6] = { 0,5,5,5,5,5 }; //각 색종이의 남은 개수
int res = 987654321;

// 색종이로 모두 채웠는지 확인
bool isZero() { 
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j <= 10; j++) {
			if (p[i][j] == 1) return false;
		}
	}
	return true;
}

// (x,y)에서 size 크기만큼의 색종이를 채울 수 있는가 확인
bool isPossible(int x, int y, int size) { 
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (p[i][j] == 0) return false;
		}
	}
	return true;
}

// 다음으로 채워야 할 위치 확인
pair<int, int> checkPos() {
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j <= 10; j++) {
			if (p[i][j] == 1) return { i,j };
		}
	}
}

void fill(int x, int y, int size, int color) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			p[i][j] = color;
		}
	}
}

void dfs(int cnt) {
	if (isZero()) { //종료조건
		res = min(res, cnt);
		return;
	}

	pair<int, int> pos = checkPos(); //색종이를 채워야 하는 다음 위치 검색
	for (int i = 5; i >= 1; i--) {
		if (paper[i] == 0) continue; // 색종이가 안 남아있으면 제외
		if (pos.first + i > 11 || pos.second + i > 11) continue; //경게 벗어나면 제외
		if (isPossible(pos.first, pos.second, i)) {
			paper[i]--; // i 크기의 색종이 개수 -1
			fill(pos.first, pos.second, i, 0); // 0으로 색종이를 덮는다.
			dfs(cnt + 1);
			fill(pos.first, pos.second, i, 1); // 1로 다시 복구
			paper[i]++; // i 크기의 색종이 개수 복구
		}
		continue;
	}
}

int main()
{
	for (int i = 1; i <= 10; i++)
		for (int j = 1; j <= 10; j++)
			cin >> p[i][j];

	dfs(0);

	if (res == 987654321) cout << "-1";
	else cout << res;
}