boj, 백준) 21611. 마법사 상어와 블리자드 ( C/C++)

1. 문제 링크

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

21611번: 마법사 상어와 블리자드

2. 문제 개요

가장 처음에 상어가 있는 칸을 제외한 나머지 칸에는 구슬이 하나 들어갈 수 있다. 1, 2, 3번 구슬이 들어갈 수 있고 같은 번호를 가진 구슬이 번호가 연속하는 칸에 있으면 그 구슬을 연속하는 구슬이라고 한다.

 

블리자드 마법을 시전 하려면 방향 d와 거리 s를 정해야한다. 4가지 방향이 있고 상 하 좌 우, 1 2 3 4로 표현한다.

블리자드 마법은 방향 d의 거리 s이내인 구슬을 파괴한다.

 

구슬이 파괴되어 빈칸이 생기면 앞으로 이동한다.

 

연속하는 구슬이 4개 이상일 때, 구슬은 폭발한다. 구슬이 폭발하면 그 칸은 빈칸이 된다.

 

빈칸은 다시 뒤의 구슬로 메꿔지고, 또 구슬이 4개 이상이라면 구슬은 폭발한다. 폭발할 수 있는 구슬이 없을 때까지 반복된다.

 

구슬은 두개로 나뉘는데 첫 번째 구슬은 묶인 구슬의 개수, 두 번째 구슬은 구슬의 번호다. 나뉘는데 맵을 초과 한다면 구슬은 더 이상 나뉘지 않는다.

 

3. 문제 힌트

문제가 너무 길어 개요에 정말 간단하게 썼다.

 

골자를 다시한번 말하면,

1) 그리드 형태 (사각형 격자)의 주어진 맵을 직선으로 펴기

2) 블리자드 마법 쓰는 곳 구하기

3) 블리자드 마법 쓰기 (m번)

   4) 구슬 폭파하기 (가능할 때까지)

   5) 구슬 당기기

   6) 구슬 분리(확장)하기

 

 

특별한 알고리즘이 들어가는 문제는 아니다. 규칙을 잘 찾아서 1), 2) step만 잘 처리해준다면 3, 4, 5, 6은 간단하게 구현할 수 있다.

 

4. 문제 풀이

맞왜틀만 몇시간째 하다가 코드 다 지우고 다음날 다시 구현하니 정답으로 나와 허무했던 문제.. 실전에서도 맞왜틀 나오면 조금 보다가 그냥 지우고 처음부터 다시 시작하는게 정신건강에도 좋다. 맞왜틀 조차 나오면 안 되지만 ㅠ..

 

 

이 문제의 핵심은 

사각형 형태의 맵을 직선으로 펴는 것, 블리자드 마법을 쓸 때, 어떤 칸이 지워지는지 이 두 개만 잘 구현하면 문제는 정말 쉽게 풀린다.

 

사각형의 맵을 직선으로 푸는 데는 규칙이 있다.

규칙

좌표는 (0,0) ~ (n-1, n-1)을 기준으로 합니다.

 

처음 좌표 (n-1)/2, (n-1)/2에서 시작해서, 방향은 왼쪽, 밑, 오른쪽, 위 순서대로 진행한다.

그러면 왼쪽으로 1칸, 밑으로 1칸, 오른쪽으로 2칸, 위로 2칸, 왼 3칸, 밑 3칸, ... 이렇게

1,1 2,2 3,3 4,4,4 마지막은 3번 이런 식으로 격자형 맵을 직선으로 만들어 줄 수 있다.

 

 

 

 

다음은 직선 형태의 맵에서, 블리자드가 시전 될(?) index를 구하는 방법이다.

규칙

이번에도 중심 상어 (0번)를 기준으로,

1

2 2 2

3

4 4 4

5

6 6 6

...

과 같은 순서로 index가 증가하는 규칙을 찾을 수 있다.

 

 

다음은 직선 형태로 된 맵에서 '구슬이 몇 개 연속으로 존재하는지'를 구분하는 방법이다.

 

밑의 코드에서는 l, r처럼 2개의 위치를 사용해서 1차원 배열(vector)에서 sliding window처럼 움직이도록 했다.

배열에서 l번째 값을 기준으로 놓고, 배열에서 r번째 값이 같다면 다음칸으로 이동,

그렇지 않다면 혹시 4개 이상인지, 4개 이상이라면 폭발, 4개 이상이 아니라면 l=r을 두어 window의 크기를 줄이는 방식이다.

 

이 문제는 특정 알고리즘을 요하는 문제는 아니라서 풀이에 여러 가지 방법이 존재한다.

여튼, 밑의 코드는 위의 아이디어를 중심으로 구현했다.

 

그리고 큰~~ 시간 차이는 없겠지만 원래,

폭발 - 당기기 - 폭발 - 당기기.. 이런 순서로 구현해도 된다, 하지만 복사가 많이 될 것 같아서 당기는 부분은 제거하고 '폭발했음'을 의미하는 값을 넣고 폭발만 하도록 했다.

그런데 구슬의 최대 개수가 n^2개라 폭발-당기기-폭발-당기기.. 형태로 해도 시간 초과가 나올 것 같지는 않다.

 

5. 코드

#include <cstdio>
#include <vector>
using namespace std;

int gridMap[50][50];
vector<int> linearMap, blizardLocation[4];//상하좌우
int m, n;
int explosion[4];
constexpr int removedBlock = -1;


void convertGridToLinear()
{
	constexpr int dx[] = { -1,0,1,0 };
	constexpr int dy[] = { 0,1,0,-1 };

	int cy = (n - 1) / 2;
	int cx = (n - 1) / 2;

	int dir = 0;

	linearMap.push_back(0);	//shark
	int cnt = 2;

	for (int dist = 1; dist <= n - 1; ++dist){

		if (dist == n - 1)
			cnt = 3;

		for (int i = 0; i < cnt; ++i) {
			for (int j = 0; j < dist; ++j) {
				cy += dy[dir];
				cx += dx[dir];
				if (gridMap[cy][cx] != 0)
					linearMap.push_back(gridMap[cy][cx]);
			}
			dir = (dir + 1) % 4;
		}
	}
}
void getBlizardLocation()
{
	int weight = 0;
	int dir = 0;
	int order[] = { 2,1,3,0 };

	for (int loc = 0; loc < n*n;)
	{
		if (dir == 0)
		{
			++weight;
			loc += weight;
			if (loc >= n*n)
				break;
			blizardLocation[order[dir]].push_back(loc);
			++weight;
			dir = (dir + 1) % 4;
		}
		else
		{
			loc += weight;
			if (loc >= n*n)
				break;
			blizardLocation[order[dir]].push_back(loc);
			dir = (dir + 1) % 4;
		}
	}
}
bool explodeBlock()
{
	bool isexplode = false;
	int l = 0, r = 0;
	int blockNum = 0;

	while (r < linearMap.size()){
		
		if (linearMap[l] == linearMap[r] || linearMap[r] == removedBlock)
		{
			if (linearMap[l] == linearMap[r])
				++blockNum;

			++r;
			if (r == linearMap.size() && blockNum >= 4)
			{
				for (int i = l; i < r; ++i) {
					if(linearMap[i] != removedBlock)
						++explosion[linearMap[i]];
					linearMap[i] = removedBlock;
				}
				isexplode = true;
				l = r;
				break;
			}
		}
		else
		{
			if (blockNum >= 4)
			{
				for (int i = l; i < r; ++i) {
					if (linearMap[i] != removedBlock)
						++explosion[linearMap[i]];
					linearMap[i] = removedBlock;
				}
				isexplode = true;
			}
			l = r;
			blockNum = 0;
		}
	}
	return isexplode;
}
void pullBlocks()
{
	vector<int> temp = linearMap;
	linearMap.clear();

	for (int item : temp)
		if (item != removedBlock)
			linearMap.push_back(item);
}
void extension() 
{
	vector<int> temp = linearMap;

	linearMap.clear();
	linearMap.push_back(0);	//shark

	int l = 1, r = 1;

	while (r < temp.size())
	{
		if (temp[l] == temp[r])
		{
			++r;

			if (r == temp.size())
			{
				int num = r - 1 - l + 1;

				if (linearMap.size() < n * n)
					linearMap.push_back(num);

				if (linearMap.size() < n * n)
					linearMap.push_back(temp[l]);

				l = r;
			}
		}
		else
		{
			int num = r - 1 - l + 1;

			if (linearMap.size() < n * n)
				linearMap.push_back(num);

			if (linearMap.size() < n * n)
				linearMap.push_back(temp[l]);

			l = r;
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%d", &gridMap[i][j]);

	convertGridToLinear();
	getBlizardLocation();


	while (m--)
	{
		int d, s;
		scanf("%d %d", &d, &s);

		for (int i = 0; i < s; ++i) 
			if (blizardLocation[d - 1][i] < linearMap.size())
				linearMap[blizardLocation[d - 1][i]] = removedBlock;
		

		while (explodeBlock()) {}

		pullBlocks();

		extension();

	}

	printf("%d", explosion[1] + explosion[2] * 2 + explosion[3] * 3);
		
	return 0;
}

6. 결과