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

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

풀이과정 (완전탐색)

주어진 종이에 1로 채워진 칸을 주어진 색종이를 이용하여 가장 적은 수로 붙일 수 있는 경우를 구하면 된다.

 

1. 모든 경우를 따져야한다. 따라서 1로 채워진 칸을 pos 벡터에 담았다.

 

2. 현재 pos에서 사용 할 수 있는 색종이를 찾아 붙여 나갔다. 사용 된 칸이라면 다음 pos로 넘어간다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <string.h>
#define MAX_MAP_SIZE 10
#define MAX_PAPER_SIZE 5
#define MAX_PAPER_COUNT 5
using namespace std;
int map[10][10];
int visited[10][10];
int color[5];
vector<pair<int, int>> pos;
int answer = 987654321;
int paperTotal = 0;

int findMaxSquare(int x, int y, int size)
{
	if (x + size > MAX_MAP_SIZE || y + size > MAX_MAP_SIZE) return 0;
	for (int r = y; r < y + size; r++) {
		for (int c = x; c < x + size; c++) {
			if (map[r][c] == 0 || visited[r][c] == 1) {
				return 0;
			}
		}
	}
	return 1;
}

void maskSquare(int x, int y, int size) {
	for (int r = y; r < y + size; r++) {
		for (int c = x; c < x + size; c++) {
			visited[r][c] = 1;
		}
	}
}

void solution(int depth, int sum)
{
	if (depth == paperTotal) {
		if (answer > sum) {
			answer = sum;
		}
		return;
	}
	
	pair<int, int> curPos = pos[depth];
	if (visited[curPos.first][curPos.second] == 1) {
		solution(depth + 1, sum);
	}
	else {
		int visitedCpy[10][10] = { 0, };
		memcpy(visitedCpy, visited, sizeof(visited));
		for (int j = MAX_PAPER_SIZE; j >= 1; j--) {
			if (color[j - 1] >= MAX_PAPER_COUNT) continue;
			if (findMaxSquare(curPos.second, curPos.first, j)) {
				color[j - 1] += 1;
				maskSquare(curPos.second, curPos.first, j);
				solution(depth + 1, sum + 1);
				memcpy(visited, visitedCpy, sizeof(visited));
				color[j - 1] -= 1;
			}
		}
	}
}

int main()
{
	for (int i = 0; i < MAX_MAP_SIZE; i++) {
		for (int j = 0; j < MAX_MAP_SIZE; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) {
				pos.push_back(make_pair(i, j));
			}
		}
	}
	if (pos.empty()) {
		printf("0\n");
	}
	else {
		paperTotal = pos.size();
		solution(0, 0);
		printf("%d\n", answer == 987654321 ? -1 : answer);
	}
	return 0;
}

 

결과