BOJ 백준 17136 색종이 붙이기

 

#include <stdio.h>
#include <vector>
#include <memory.h>

using namespace std;

const int SIZE = 10;
int arrMap[SIZE][SIZE];
bool arrBoolMap[SIZE][SIZE];
int arrCount[5];

struct EmptySpace { int x, y; };
vector<EmptySpace>	vecEmptySpaces;

int		g_nCnt = 999999999;
int		g_nRemainArea = 0;
bool	g_bFind = false;

void Input()
{
	for (int i = 0; i < SIZE; ++i)
	{
		for (int j = 0; j < SIZE; ++j)
		{
			scanf("%d", &arrMap[i][j]);
			if (arrMap[i][j])
			{
				g_nRemainArea++;
				vecEmptySpaces.push_back({ i, j });
			}
		}
	}

	for (int i = 0; i < 5; ++i)
		arrCount[i] = 5;
}

bool CheckArea(int x, int y, int n)
{
	int xLimit = x + n;
	int yLimit = y + n;
	if (xLimit > SIZE || yLimit > SIZE)
		return false;

	for (int i = x; i < xLimit; ++i)
	{
		for (int j = y; j < yLimit; ++j)
		{
			if (arrBoolMap[i][j] || !arrMap[i][j])
				return false;
		}
	}
	return true;
}

int ChangeBoolMap(int x, int y, int n, bool b)
{
	int xLimit = x + n;
	int yLimit = y + n;
	int nCnt = 0;

	for (int i = x; i < xLimit; ++i)
	{
		for (int j = y; j < yLimit; j++)
		{
			arrBoolMap[i][j] = b;
			if (arrMap[i][j])
				nCnt++;
		}
	}
	return nCnt;
}

// 시작점, 사용한 종이 개수, 비어있는 공간의 수
void solution(int nIdx, int nCnt, int nRemain)
{
	if (nRemain == 0)
	{
		g_bFind = true;
		if (g_nCnt > nCnt)
			g_nCnt = nCnt;
		return;
	}

	if (nCnt >= g_nCnt)
		return;

	int cur_x = vecEmptySpaces[nIdx].x;
	int cur_y = vecEmptySpaces[nIdx].y;

	// 종이가 붙여져 있는 곳인 경우
	if (arrBoolMap[cur_x][cur_y])
		solution(nIdx + 1, nCnt, nRemain);

	for (int j = 0; j <= 4; ++j)
	{
		if (arrCount[j] && CheckArea(cur_x, cur_y, j + 1))
		{
			arrCount[j]--;
			int nRemove = ChangeBoolMap(cur_x, cur_y, j + 1, true);

			solution(nIdx + 1, nCnt + 1, nRemain - nRemove);

			ChangeBoolMap(cur_x, cur_y, j + 1, false);
			arrCount[j]++;
		}
	}
}

void PrintResult()
{
	if (g_bFind)
	{
		printf("%d\n", g_nCnt);
	}
	else
	{
		printf("-1\n");
	}
}

int main()
{
	Input();
	solution(0, 0, g_nRemainArea);
	PrintResult();
	return 0;
}

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

17136번: 색종이 붙이기

문제 풀이)

    1. 입력을 받으면서 색종이를 붙여야 할 점의 좌표를 벡터에 push해주고,

       색종이를 붙여야 할 점(1)의 총 개수를 저장한다.

 

    int nIdx : 색종이를 붙여야할 점들이 저장되어 있는 벡터의 index

    int nCnt = 현재까지 사용한 종이의 개수

    int nRemain : 남아 있는 색종이를 붙여야 할 점의 개수

 

    2. 재귀 방식으로, 인자로는 ( nIdx, nCnt, nRemain ) 이렇게 총 3가지이다.

 

    3. 만약 nRemain이 0이라면, 모든 공간에 색종이를 붙인 것이므로 방법을 찾았음을 표시하고

       최소 색종이의 수를 저장하는 변수와 비교하여 더 적을 경우 갱신해준다.

       nRemain이 0이 아니라면 색종이를 더 붙여야 하므로 4번으로 넘어간다.

 

    4. 색종이를 붙이기 전에, 해당 점이 이미 색종이로 덮여있는 지 확인하고, 덮여져 있다면 다음 점으로 넘어간다(3번)

       만약 덮여있지 않다면, 5번으로 넘어간다.

 

    5. 해당 점에 대해 5가지의 색종이를 모두 붙여보는 완전탐색을 이용한다.