[백준] 18808 스티커 붙이기 (C++)

백준 18808 스티커 붙이기

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

시뮬레이션 문제로 스티커를 회전시키고, 붙일 수 있는지 확인하는 코드를 짜는 게 핵심이었다. 

 

1. 스티커를 k개 입력받는 동안 스티커의 행과 열을 업데이트하면서 새로운 스티커를 배열에 담는다. 

2. 입력받은 스티커를 노트북에 붙일 수 있는지 확인해야 하므로, 스티커의 크기만큼 노트북 크기에 들어가는지 체크한다. 

//스티커를 떼서 붙일 수 있는지 확인하고 붙이기
bool attach()
{
	for (int i = 0; i < n-r+1; ++i)
	{
		for (int j = 0; j < m-c+1; ++j)
		{
			if (check(i, j))
			{
				sticking(i, j);
				return true;
			}
		}
	}
	return false;
}

3. 입력받은 행과 열을 기준으로 스티커 배열에 스티커가 있고, 이미 노트북에 스티커가 붙여져 있다면 false를 리턴한다. 이외의 경우 스티커를 붙일 수 있으므로 true를 리턴한다.  

//스티커를 붙일 수 있는 지 확인
bool check(int rr, int cc)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			int nextR = i + rr;
			int nextC = j + cc;
			if (sticker[i][j] == 1 && book[nextR][nextC] == 1)
				return false;
		}
	}
	return true;
}

4. 해당 행과 열을 기준으로 스티커의 크기만큼 노트북에 스티커를 붙인다. 

//스티커를 붙임
void sticking(int rr, int cc)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			int nextR = i + rr;
			int nextC = j + cc;
			if (sticker[i][j] == 1)
				book[nextR][nextC] = 1;
		}
	}
}

5. bool 함수를 사용하여 스티커를 붙였다면 true를 리턴해 continue 해주고, 붙이지 못했다면 false를 리턴하여 스티커를 회전시킨다. 

bool isAttach = attach();
		if (isAttach)
			continue;

6. 스티커를 90도->180도->270도 순서대로 회전시키는데, 만약 회전 후에 스티커를 붙일 수 있다면 바로 break해준 후 노트북에 스티커가 붙여진 수를 계산해주면 된다. 스티커를 붙일 수 없다면 다시 회전시킨다.

//회전(90->180->270)
for (int k = 0; k < 3; ++k)
{
	rotation();
	isAttach = attach();
	if (isAttach)
		break;
}

void rotation()
{
	int tmp[MAX][MAX] = { 0, };
	//시계방향으로 회전
	for (int i = 0; i < c; ++i)
	{
		for (int j = 0; j < r; ++j)
		{
			tmp[i][r - 1 - j] = sticker[j][i];
		}
	}
	for (int i = 0; i < MAX; ++i)
	{
		for (int j = 0; j < MAX; ++j)
		{
			sticker[i][j] = tmp[i][j];
		}
	}
	swap(r, c);
}

3. 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define MAX 41
#define INF 987654321
using namespace std;
int n, m, r ,c, k;
int sticker[MAX][MAX];
int book[MAX][MAX];
bool checked[41][41];
//초기화
void init()
{
	for (int i = 0; i < MAX; ++i)
	{
		for (int j = 0; j < MAX; ++j)
		{
			sticker[i][j] = 0;
		}
	}
}
//스티커 붙인 공간 계산
int calc()
{
	int cnt=0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (book[i][j] == 1)
				cnt++;
		}
	}
	return cnt;
}
void rotation()
{
	int tmp[MAX][MAX] = { 0, };
	//시계방향으로 회전
	for (int i = 0; i < c; ++i)
	{
		for (int j = 0; j < r; ++j)
		{
			tmp[i][r - 1 - j] = sticker[j][i];
		}
	}
	for (int i = 0; i < MAX; ++i)
	{
		for (int j = 0; j < MAX; ++j)
		{
			sticker[i][j] = tmp[i][j];
		}
	}
	swap(r, c);
}
//스티커를 붙일 수 있는 지 확인
bool check(int rr, int cc)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			int nextR = i + rr;
			int nextC = j + cc;
			if (sticker[i][j] == 1 && book[nextR][nextC] == 1)
				return false;
		}
	}
	return true;
}
//스티커를 붙임
void sticking(int rr, int cc)
{
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			int nextR = i + rr;
			int nextC = j + cc;
			if (sticker[i][j] == 1)
				book[nextR][nextC] = 1;
		}
	}
}
//스티커를 떼서 붙일 수 있는지 확인하고 붙이기
bool attach()
{
	for (int i = 0; i < n-r+1; ++i)
	{
		for (int j = 0; j < m-c+1; ++j)
		{
			if (check(i, j))
			{
				sticking(i, j);
				return true;
			}
		}
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;

	for (int i = 0; i < k; ++i)
	{
		init();	
		cin >> r >> c;
		for (int sr = 0; sr < r; ++sr)
		{
			for (int sc = 0; sc < c; ++sc)
			{
				cin >> sticker[sr][sc];
			}
		}

		bool isAttach = attach();
		if (isAttach)
			continue;
		//회전(90->180->270)
		for (int k = 0; k < 3; ++k)
		{
			rotation();
			isAttach = attach();
			if (isAttach)
				break;
		}
	}
	cout << calc() << "\n";
	return 0;
}

4. 결과