스티커 붙이기_백준 18808번

2020-04-02 · 배운 것 · 6분 읽기

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

1. 풀이방법

풀이방법 자체는 간단하다.
1) 스티커를 0도, 90도, 180도, 270도 순으로 돌리며 만약 스티커를 붙일수 있으면 붙이기
2) 다 돌려봐도 붙일수 없다면 버리기

그리고 이 동작들을 수행하기 위해서 함수를 여러개 만들었다.
90도 회전시켜 반환하는 함수, 자리가 있는지 확인하는 함수, 스티커를 붙이는 함수 까지 다 따로 만들어 조합해서 문제를 풀었다.

2. 코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M;
int map[42][42];
int CheckMap[42][42];
int numOfsticker;
vector<vector<int>> sticker;

void CheckMapInit()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			CheckMap[i][j] = map[i][j];
}

vector<vector<int>> rotate90(int n, int m)
{
	vector<vector<int>> after;
	after.resize(m);
	for (int i = 0; i < m; i++)
		after[i].resize(n + 1);

	for (int j = 0; j < m; j++)
		for (int i = n - 1; i >= 0; i--)
			after[j][n - 1 - i] = sticker[i][j];

	return after;
}

//자리가 있는지 확인
bool isPossible(int n, int m, int y, int x)
{
	CheckMapInit();

	//일단 범위 안인지 확인
	if (n + y > N || m + x > M)
		return false;

	//자리가 있는지 확인
	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + m; j++)
		{
			int si = i - y;
			int sj = j - x;
			//스티커를 붙여야할 자리에 이미 map에 스티커가 붙어 있다면
			if (sticker[si][sj] == 1)
			{
				if (CheckMap[i][j] == 1)
					return false;
			}
		}
	}
	
	return true;
}

void attach(int n, int m, int y, int x)
{
	//자리가 있는지 확인
	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + m; j++)
		{
			int si = i - y;
			int sj = j - x;
			//스티커를 붙여야할 자리에 붙이기
			if (sticker[si][sj] == 1)
				map[i][j] = 1;
		}
	}
}

bool attachSticker(int n, int m)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//붙을수 있으면
			if (isPossible(n, m, i, j))
			{
				//붙이셈
				attach(n, m, i, j);
				return true;
			}
		}
	}
	//끝까지 못붙였으면
	return false;
}

void stikerInit()
{
	//sticker 공간확보
	sticker.resize(12);
	for (int s = 0; s < 12; s++)
		sticker[s].resize(12);
}

void stikerErase(int n, int m)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			sticker[i][j] = 0;
}

int main()
{
	cin >> N >> M >> numOfsticker;

	int n, m;
	for (int cnt = 0; cnt < numOfsticker; cnt++)
	{
		cin >> n >> m;

		stikerInit();

		int value;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> value;		
				sticker[i][j] = value;
			}
		}
		
		//여기서 함 붙여봐라, 4방향 회전도 시켜야함..
		for (int cnt = 0; cnt < 4; cnt++)
		{
			if (cnt != 0)
			{
				sticker = rotate90(n, m);
				swap(n, m);
			}

			//붙였으면
			if (attachSticker(n, m))
				break;
		}
		stikerErase(n, m);
	}

	//다끝난후 map탐색
	int cnt = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (map[i][j] == 1)
				cnt++;

	cout << cnt; 
	return 0;
}

3. 후기

문제 구현자체는 금방했다..
근데 계속 에러가 나서 debuger를 돌려보니 에러메시지는 vector range오류인데 debug에 찍히는건 이상하게도 cin >> value; 부근에서 계속 멈췄다.
이게 뭔가하고 한참을 삽질했지만 결국 어디서 에러났나 찾았다.
오류는 cin>>value; 와는 저~ 멀리 떨어진 rotate90 함수에서 범위를 잘못구해준 오류가 있었다..
지금까지 오류날때마다 debuger에 의존했었는데 피봤다.. 이제부터 debuger는 참고만 해야겠다.