백준 17136. 색종이 붙이기

색종이 붙이기

 

---

Problem?

문제.

 

Solution

브루트 포스

dfs를 통한 탐색

색종이 크기안에 빈칸(0)이 있는 경우나 색종이를 잘 붙인 경우는 효율적으로 다음 dfs를 설정한다.

 

가정 dfs() : 갈 수 있는 경로 탐색   board : 맵 confetti : 남은 색종이 파악 answer : 최소 경우의 답 보관

Code

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

#define MAX 10
#define INF 999999999

int board[MAX][MAX];					// map
int confetti[6] = { 0, 5, 5, 5, 5, 5 };	// confetti count(count per paper)
int answer = INF, cnt = 0;					// answer

void dfs(int y, int x){
	// if line is end
	if (x == MAX) {
		dfs(y + 1, 0);
		return;
	}
	// end state
	if (y == MAX) {
		answer = min(answer, cnt);
		return;
	}
	// if board is empty, check the next position
	if (board[y][x] == 0) {
		dfs(y, x + 1);
		return;
	}

	// check all possibility (loop : len 5 -> 1)
	for (int l = 5; l >= 1; l--) {
		if (confetti[l] == 0 || y + l > MAX || x + l > MAX)
			continue;
		
		bool flag = false;
		for (int i = y; i < y + l; i++){
			for (int j = x; j < x + l; j++){
				if (board[i][j] == 0) {
					flag = true;
					break;
				}
			}
			if (flag == true)
				break;
		}
		if (flag == true)
			continue;

		confetti[l]--;
		cnt++;
		for (int i = y; i < y + l; i++)
			for (int j = x; j < x + l; j++)
				board[i][j] = 0;

		// efficient way
		dfs(y, x + l);

		for (int i = y; i < y + l; i++)
			for (int j = x; j < x + l; j++)
				board[i][j] = 1;
		cnt--;
		confetti[l]++;
	}
}

int main() {
	// input
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			scanf("%d", &board[i][j]);

	// solution
	dfs(0, 0);
	if (answer == INF)
		answer = -1;

	// output
	cout << answer << "\n";

	return 0;
}

 

---