[백준/BOJ] 백준 21611번 : 마법사 상어와 블리자드

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

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

vector<pair<int, int>> order에 빙글빙글 도는 순서대로 좌표를 순서대로 넣어놓고 이를 이용하여 문제를 해결했다. 구슬을 다루는 것은 deque를 이용했다.

 

코드

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

int n, m;
vector<vector<int>> board(50, vector<int>(50, 0));
int dxdy[5][2] = { {0,0},{-1,0},{1,0},{0,-1},{0,1} };
pair<int, int> shark;
vector<pair<int, int>> order; //빙글빙글 도는 순서대로 좌표
int result = 0;

void Throw(int d, int s)
{
	for (int i = 1; i <= s; i++)
	{
		pair<int, int> there = make_pair(shark.first + (dxdy[d][0] * i), shark.second + (dxdy[d][1] * i));

		board[there.first][there.second] = 0;
	}
}

void MakeOrder()
{
	pair<int, int> here = shark;
	int len = 1;
	int dir = 3;

	order.push_back(here);

	while (1)
	{
		for (int i = 0; i < 2; i++)
		{
			for (int j = 1; j <= len; j++)
			{

				pair<int, int> there = make_pair(here.first + (dxdy[dir][0]), here.second + (dxdy[dir][1]));
				here = there;

				order.push_back(here);
			}

			if (dir == 3)
				dir = 2;

			else if (dir == 2)
				dir = 4;

			else if (dir == 4)
				dir = 1;

			else if (dir == 1)
				dir = 3;
		}

		//오른쪽 위에 왔을때
		if (here.first == 1 && here.second == n)
			break;

		len++;
	}

	//윗줄 넣기
	for (int j = 1; j <= len; j++)
	{
		pair<int, int> there = make_pair(here.first + (dxdy[dir][0] * j), here.second + (dxdy[dir][1] * j));
		pair<int, int> here = there;

		order.push_back(here);
	}

}

void Move()
{
	while (1)
	{
		bool ret = false; //이번 움직임에 터지는게 있는지 확인

		deque<int> ball;

		for (int i = 0; i < order.size(); i++)
		{
			int this_ball = board[order[i].first][order[i].second];

			if (this_ball != 0)
				ball.push_back(this_ball);

			board[order[i].first][order[i].second] = 0;
		}

		deque<int> check;
		deque<int> next_ball;

		for (int i = 0; i < ball.size(); i++)
		{
			if (check.size() == 0)
				check.push_back(ball[i]);

			//같은 구슬일때
			else if (check[0] == ball[i])
				check.push_back(ball[i]);

			//다른 구슬일때
			else if (check[0] != ball[i])
			{
				//기존에 저장되어있는게 터지는 경우라면
				if (check.size() >= 4)
				{
					ret = true;

					result += (check[0] * check.size());

					check.clear();
				}

				//터지는 경우가 아니라면
				else
				{
					for (int j = 0; j < check.size(); j++)
						next_ball.push_back(check[j]);

					check.clear();
				}

				check.push_back(ball[i]);
			}


			//마지막일때
			if (i == ball.size() - 1)
			{
				if (check.size() >= 4)
				{
					ret = true;

					result += (check[0] * check.size());

					check.clear();
				}

				else
				{
					for (int j = 0; j < check.size(); j++)
						next_ball.push_back(check[j]);

					check.clear();
				}
			}
		}

		//구슬 재배치
		for (int i = 0; i < order.size(); i++)
		{
			if (next_ball.size() == 0)
				break;

			//상어 위치일때
			if (i == 0)
				continue;

			pair<int, int> here = order[i];

			board[here.first][here.second] = next_ball[0];
			next_ball.pop_front();
		}

		//터지는 구슬이 없을때
		if (ret == false)
			break;
	}

	deque<int> final_ball;
	deque<int> final_check;
	deque<int> final_result;

	for (int i = 0; i < order.size(); i++)
	{
		int this_ball = board[order[i].first][order[i].second];

		if (this_ball != 0)
			final_ball.push_back(this_ball);

		board[order[i].first][order[i].second] = 0;
	}

	for (int i = 0; i < final_ball.size(); i++)
	{
		if (final_check.size() == 0)
			final_check.push_back(final_ball[i]);

		//같은 구슬일때
		else if (final_check[0] == final_ball[i])
			final_check.push_back(final_ball[i]);

		//다른 구슬일때
		else if (final_check[0] != final_ball[i])
		{
			final_result.push_back(final_check.size());//구슬의 개수
			final_result.push_back(final_check[0]);//구슬의 번호

			final_check.clear();
			final_check.push_back(final_ball[i]);
		}


		//마지막일때
		if (i == final_ball.size() - 1)
		{
			final_result.push_back(final_check.size());//구슬의 개수
			final_result.push_back(final_check[0]);//구슬의 번호

			final_check.clear();
		}
	}

	//구슬 재배치
	for (int i = 0; i < order.size(); i++)
	{
		if (final_result.size() == 0)
			break;

		//상어 위치일때
		if (i == 0)
			continue;

		pair<int, int> here = order[i];

		board[here.first][here.second] = final_result[0];
		final_result.pop_front();
	}

}

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

	cin >> n >> m;

	shark = make_pair((n + 1) / 2, (n + 1) / 2);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	MakeOrder();

	for (int i = 0; i < m; i++)
	{
		int d, s;
		cin >> d >> s;

		Throw(d, s);
		Move();
	}

	cout << result;

	return 0;
}