[백준/BOJ] 백준 18808번 : 스티커 붙이기

www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

순서대로 붙일 스티커를 확인하는데, 해당 위치에 스티커를 붙일 수 있는지 확인할 때와, 스티커를 붙일 때 스티커의 행렬 형태를 이용하지 않고, 스티커의 행렬 형태를 좌표 형태로 바꿔서 이용했다. 스티커를 회전할 때는 스티커의 행렬 형태를 이용했다.

 

코드

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

int n, m, k;
int notebook[40][40];
vector<vector<vector<int>>> sticker;

void Pre()
{
	for (int i = 0; i < 40; i++)
		for (int j = 0; j < 40; j++)
		{
			notebook[i][j] = 0;
		}
}

//행렬형태로 되어 있는 스티커를 좌표형태로 변환해서 반환한다
vector<pair<int, int>> sticker_xyMake(vector<vector<int>> this_sticker)
{
	vector<pair<int, int>> ret;
	pair<int, int> standard; //기준 좌표
	bool find_standard = false;

	for (int i = 0; i < this_sticker.size(); i++)
	{
		for (int j = 0; j < this_sticker[0].size(); j++)
		{
			if (this_sticker[i][j] == 1)
			{
				if (find_standard == false)
				{
					standard = make_pair(i, j);
					find_standard = true;
				}

				ret.push_back(make_pair(i - standard.first, j - standard.second)); //기준 좌표를 기준으로 한 좌표형태로 구한다
			}
		}
	}

	return ret;
}

//스티커를 회전한 값을 반환한다
vector<vector<int>> Turn(vector<vector<int>> this_sticker)
{
	vector<vector<int>> ret(this_sticker[0].size(), vector<int>(this_sticker.size(), 0));

	for (int i = 0; i < this_sticker.size(); i++)
		for (int j = 0; j < this_sticker[0].size(); j++)
		{
			ret[j][this_sticker.size() - 1 - i] = this_sticker[i][j];
		}

	return ret;
}

//x,y위치를 기준으로 해당 스티커를 붙인다
void Stick(int x, int y, vector<pair<int, int>> this_sticker_xy)
{
	for (int i = 0; i < this_sticker_xy.size(); i++)
	{
		notebook[x + this_sticker_xy[i].first][y + this_sticker_xy[i].second] = 1;
	}
}

//x,y위치를 기준으로 해당 스티커를 붙일 수 있는지 확인
bool canStick(int x, int y, vector<pair<int, int>> this_sticker_xy)
{
	for (int i = 0; i < this_sticker_xy.size(); i++)
	{
		//범위를 넘어갈때
		if (x + this_sticker_xy[i].first < 0 || x + this_sticker_xy[i].first >= n || y + this_sticker_xy[i].second < 0 || y + this_sticker_xy[i].second >= m)
			return false;

		//해당위치에 이미 스티커가 붙어있을때
		if (notebook[x + this_sticker_xy[i].first][y + this_sticker_xy[i].second] == 1)
			return false;
	}

	return true;
}

//select_number:확인할 스티커 번호, turn_num:지금 스티커를 몇번 회전했는지
int Solve(int select_number, int turn_num)
{
	int ret = 0;

	//모든 스티커를 다 확인했을때
	//스티커가 붙은 칸의 수를 센다
	if (select_number == sticker.size())
	{
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (notebook[i][j] == 1)
					ret++;

		return ret;
	}

	vector<pair<int, int>> this_sticker_xy = sticker_xyMake(sticker[select_number]); //스티커를 좌표형태로 변환한다
	pair<int, int> stick_point;
	bool stick_point_find = false;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//스티커를 붙일 수 있는 위치를 찾았을때
			if (notebook[i][j] == 0 && canStick(i, j, this_sticker_xy))
			{
				stick_point = make_pair(i, j);
				stick_point_find = true;
				break;
			}
		}

		if (stick_point_find == true)
			break;
	}

	if (stick_point_find == true)
	{
		//해당위치에 스티커를 붙인다
		Stick(stick_point.first, stick_point.second, this_sticker_xy);

		//다음 스티커를 확인한다
		ret = Solve(select_number + 1, 0);
	}

	//해당 스티커를 붙일 위치를 찾지 못했을때
	if (stick_point_find == false)
	{
		//4번째 회전했을때
		if (turn_num == 4)
		{
			ret = Solve(select_number + 1, 0);
		}

		else
		{
			//해당 스티커를 회전한다
			sticker[select_number] = Turn(sticker[select_number]);

			ret = Solve(select_number, turn_num + 1);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int r, c;
	int input;

	cin >> n >> m >> k;

	for (int i = 0; i < k; i++)
	{
		vector<vector<int>> this_sticker;

		cin >> r >> c;

		for (int j = 0; j < r; j++)
		{
			vector<int> this_sticker_row;
			for (int l = 0; l < c; l++)
			{
				cin >> input;
				this_sticker_row.push_back(input);
			}
			this_sticker.push_back(this_sticker_row);
		}

		sticker.push_back(this_sticker);
	}

	Pre();

	cout << Solve(0, 0);

	return 0;
}