[알고리즘] 색종이 붙이기

구현 방식

• 백트래킹을 이용해서 완전탐색한다.
• 현재 위치에서 특정 크기의 종이로 채울 수 있다면, 종이로 채운 부분을 visited 에 true로 변경하고 백트래킹 함수를 호출한다.
• visited 에 true로 변경한 부분은 다시 false로 변경해준다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

const int MAXSIZE = 5;
const int BOARDSIZE = 10;
int board[BOARDSIZE][BOARDSIZE];
int result = INT_MAX;

bool visited[BOARDSIZE][BOARDSIZE] = {};

int main() {

	for (int i = 0; i < BOARDSIZE; i++)
		for (int j = 0; j < BOARDSIZE; j++)
			cin >> board[i][j];
	solution();
}


void solution()
{
	map<int,int> squares = { {1,MAXSIZE},{2,MAXSIZE} ,{3,MAXSIZE} ,{4,MAXSIZE},{5,MAXSIZE}};
	backtrk({ 0,0 }, squares);
	if (result == INT_MAX)
		cout << -1;
	else
		cout << result;
	return;
}

void backtrk(pair<int,int> currPos, map<int,int>& squares)
{
	updateCurrPos(currPos);
	if (currPos.first == -1 && currPos.second == -1)
	{

		int tmp = 0;
		for_each(squares.begin(), squares.end(), [&tmp](pair<const int, int>& square) {tmp += (MAXSIZE - square.second); });
		result = min(tmp, result);
		return;
	}
	for (auto& square : squares)
	{
		if (0 < square.second && isEmpty(currPos, square.first))
		{
			fillBoard(currPos, square.first, true);
			square.second--;
			backtrk(currPos, squares);
			square.second++;
			fillBoard(currPos, square.first, false);

		}
	}
}

void updateCurrPos(pair<int, int>& currPos)
{
	// 현재 위치에서부터 BOARDSIZE , BOARDSIZE 까지 방문되지 않았고, 1 인경우 탐색
	for (int k = currPos.first * currPos.second; k < BOARDSIZE * BOARDSIZE; k++)
	{
		int i = k / BOARDSIZE;
		int j = k % BOARDSIZE;
		if (board[i][j] == 1 && !visited[i][j])
		{
			currPos = { i,j };
			return;
		}
	}


	currPos = { -1,-1 };
}

bool isEmpty(pair<int, int>& pos, int Size)
{
	if (BOARDSIZE < pos.first + Size) return false;
	if (BOARDSIZE < pos.second + Size) return false;

	for(int i = pos.first; i < pos.first + Size; i++)
		for (int j = pos.second; j < pos.second + Size; j++)
		{
			if (visited[i][j]) return false;
			if (board[i][j] == 0) return false;
		}
	return true;
 }

void fillBoard(pair<int, int>& pos, int Size, bool value)
{
	for (int i = pos.first; i < pos.first + Size; i++)
		for (int j = pos.second; j < pos.second + Size; j++)
			visited[i][j] = value;


}