BOJ 21611. 마법사 상어와 블리자드

24-03-22

🙇‍♀️[Gold I] 마법사 상어와 블리자드 - 21611

문제 링크

성능 요약

메모리: 2160 KB, 시간: 516 ms

분류

구현, 시뮬레이션

제출 일자

2024년 3월 22일 17:02:55

문제 설명

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이며 마법사 상어는 ((N+1)/2, (N+1)/2)에 있다.

일부 칸과 칸 사이에는 벽이 세워져 있으며, 다음은 N = 3, 5, 7인 경우의 예시이다. 실선은 벽이고, 점선은 벽이 아니다. 칸에 적혀있는 수는 칸의 번호이다.


N = 3	N = 5	N = 7

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

블리자드 마법을 시전하려면 방향 d_i와 거리 s_i를 정해야 한다. 총 4가지 방향 ↑, ↓, ←, →가 있고, 정수 1, 2, 3, 4로 나타낸다. 상어는 d_i 방향으로 거리가 s_i 이하인 모든 칸에 얼음 파편을 던져 그 칸에 있는 구슬을 모두 파괴한다. 구슬이 파괴되면 그 칸은 구슬이 들어있지 않은 빈 칸이 된다. 얼음 파편은 벽의 위로 떨어지기 때문에, 벽은 파괴되지 않는다.

다음 예시는 방향은 아래, 거리는 2인 경우이다.


빨간색으로 표시된 칸에 얼음 파편이 떨어진다.	구슬이 파괴된 후

만약 어떤 칸 A의 번호보다 번호가 하나 작은 칸이 빈 칸이면, A에 있는 구슬은 그 빈 칸으로 이동한다. 이 이동은 더 이상 구슬이 이동하지 않을 때까지 반복된다. 따라서, 구슬이 파괴된 후에는 빈 칸이 생겨 구슬이 이동하고, 구슬이 모두 이동한 결과는 다음과 같다.

이제 구슬이 폭발하는 단계이다. 폭발하는 구슬은 4개 이상 연속하는 구슬이 있을 때 발생한다. 다음은 왼쪽 그림은 위의 상태에서 폭발하는 구슬이 들어있는 칸을 파란색과 초록색으로 표시한 것이고, 오른쪽 그림은 구슬이 폭발한 후의 상태이다.


구슬이 폭발하기 전	구슬이 폭발한 후

구슬이 폭발해 빈 칸이 생겼으니 다시 구슬이 이동한다. 구슬이 이동한 후에는 다시 구슬이 폭발하는 단계이고, 이 과정은 더 이상 폭발하는 구슬이 없을때까지 반복된다. 구슬이 폭발한 후의 상태에서 구슬이 이동하면 다음과 같다.

위의 상태는 4개 이상 연속하는 구슬이 있기 때문에 구슬이 다시 폭발하게 된다.


구슬이 폭발하기 전	구슬이 폭발하고 이동한 후

이제 더 이상 폭발한 구슬이 없기 때문에, 구슬이 변화하는 단계가 된다. 연속하는 구슬은 하나의 그룹이라고 한다. 다음은 1번 구슬은 빨간색, 2번 구슬은 파란색, 3번 구슬은 보라색으로 표시한 그림이다.

하나의 그룹은 두 개의 구슬 A와 B로 변한다. 구슬 A의 번호는 그룹에 들어있는 구슬의 개수이고, B는 그룹을 이루고 있는 구슬의 번호이다. 구슬은 다시 그룹의 순서대로 1번 칸부터 차례대로 A, B의 순서로 칸에 들어간다. 다음 그림은 구슬이 변화한 후이고, 색은 구분하기 위해 위의 그림에 있는 그룹의 색을 그대로 사용했다. 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.

마법사 상어는 블리자드를 총 M번 시전했다. 시전한 마법의 정보가 주어졌을 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구해보자.

입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 격자에 들어있는 구슬의 정보가 주어진다. r번째 행의 c번째 정수는 (r, c)에 들어있는 구슬의 번호를 의미한다. 어떤 칸에 구슬이 없으면 0이 주어진다. 상어가 있는 칸도 항상 0이 주어진다.

다음 M개의 줄에는 블리자드 마법의 방향 d_i와 거리 s_i가 한 줄에 하나씩 마법을 시전한 순서대로 주어진다.

출력

첫째 줄에 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력한다.

🚀풀이

3시간 컷.

빙글빙글 돌아가는 모양의 길을 따로 저장해야한다.

// load 채워주기
pair<int, int> pos = { 1, 1 };
int dy2[] = { 0, 1, 0, -1 };
int dx2[] = { 1, 0, -1, 0 };
int dir = 0;
load.push_back(pos);
visited[pos.first][pos.second] = true;
while (true)
{
    int ny = pos.first + dy2[dir];
    int nx = pos.second + dx2[dir];
    if (ny == (n + 1) / 2 && nx == (n + 1) / 2)
        break;

    if (can_go(ny, nx))
    {
        pos.first = ny;
        pos.second = nx;
        load.push_back({ pos.first, pos.second });
        visited[pos.first][pos.second] = true;
    }
    else
    {
        dir = (dir + 1) % 4;
    }
}

이렇게하면 그냥 빙글빙글 모양인데 reverse해줘야한다.

reverse(load.begin(), load.end());

정답을 구하기 위해서 아래와 같이 로직이 작동한다.

for (int i = 1; i <= m; ++i)
{
	cin >> d >> s;
	blizard();
	move();

	while (true)
	{
		if (boom())
			move();
		else
			break;
	}

	change();
}

cout << ans;

blizard는 얼음파편이 떨어져서 값을 0으로 만드는 것.
이건 쉬워서 금방 만들었다.

move에서 빈 공간을 채워주는 것으로 아래와 같이 작성했다.

void move()
{
	for (int i = 0; i < load.size(); ++i)
	{
		if (board[load[i].first][load[i].second] == 0)
		{
			for (int j = i + 1; j < load.size(); ++j)
			{
				if (board[load[j].first][load[j].second] != 0)
				{
					swap(board[load[i].first][load[i].second], board[load[j].first][load[j].second]);
					break;
				}
			}
		}
	}
}

이후 4개 이상 연속일 때 폭발을 해야한다.
폭발을 할 때 폭발하는 경우가 있다면 true를 뱉어서 반복하도록 만들었다.

bool boom()
{
	// 폭발하면 움직여야함
	bool flag = false;
	for (int i = 0; i < load.size(); ++i)
	{
		int value = board[load[i].first][load[i].second];
		int cnt = 1;
		for (int j = i + 1; j < load.size(); ++j)
		{
			if (board[load[j].first][load[j].second] != value)
			{
				if (cnt < 4)
					break;

				for (int k = i; k < j; ++k)
				{
					board[load[k].first][load[k].second] = 0;
				}
				ans += value * cnt;
				flag = true;
				i = j - 1;
				cnt = 1;
				break;
			}

			if (board[load[j].first][load[j].second] == value)
				cnt++;
		}
	}

	return flag;
}

이후에 값이 변하는 로직이 작동한다.
값이 변하는건 연속한 구슬의 개수와 구슬의 번호가 덩어리로 채워지게 된다.

void change()
{
	vector<vector<int>> cboard(n + 1, vector<int>(n + 1));
	int idx = 0;
	for (int i = 0; i < load.size();)
	{	
		if (idx >= n * n - 1)
			break;
		int value = board[load[i].first][load[i].second];
		if (value == 0)
			break;

		for (int j = i + 1; j < load.size(); ++j)
		{
			if (board[load[j].first][load[j].second] != value)
			{
				int dist = j - i;
				cboard[load[idx].first][load[idx].second] = dist;
				idx++;
				cboard[load[idx].first][load[idx].second] = value;
				idx++;
				i = j;

				break;
			}
		}
	}

	for (int i = 0; i < load.size(); ++i)
	{
		board[load[i].first][load[i].second] = cboard[load[i].first][load[i].second];
	}
}

끝!

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n, m, d, s, ans = 0;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
vector<vector<int>> board;
vector<vector<bool>> visited;
vector<pair<int, int>> load;

void move()
{
	// 맞는데 왜 틀린거야 맞잖아
	for (int i = 0; i < load.size(); ++i)
	{
		if (board[load[i].first][load[i].second] == 0)
		{
			for (int j = i + 1; j < load.size(); ++j)
			{
				if (board[load[j].first][load[j].second] != 0)
				{
					swap(board[load[i].first][load[i].second], board[load[j].first][load[j].second]);
					break;
				}
			}
		}
	}
}

bool boom()
{
	// 폭발하면 움직여야함
	bool flag = false;
	for (int i = 0; i < load.size(); ++i)
	{
		int value = board[load[i].first][load[i].second];
		int cnt = 1;
		for (int j = i + 1; j < load.size(); ++j)
		{
			if (board[load[j].first][load[j].second] != value)
			{
				if (cnt < 4)
					break;

				for (int k = i; k < j; ++k)
				{
					board[load[k].first][load[k].second] = 0;
				}
				ans += value * cnt;
				flag = true;
				i = j - 1;
				cnt = 1;
				break;
			}

			if (board[load[j].first][load[j].second] == value)
				cnt++;
		}
	}

	return flag;
}

void blizard()
{
	pair<int, int> pos = { (n + 1) / 2, (n + 1) / 2 };
	for (int i = 1; i <= s; ++i)
	{
		int ny = pos.first + dy[d - 1] * i;
		int nx = pos.second + dx[d - 1] * i;

		board[ny][nx] = 0;
	}
}

bool can_go(int y, int x)
{
	if (y < 1 || x < 1 || y > n || x > n)
		return false;
	if (visited[y][x] == true)
		return false;
	return true;
}

void change()
{
	vector<vector<int>> cboard(n + 1, vector<int>(n + 1));
	int idx = 0;
	for (int i = 0; i < load.size();)
	{	
		if (idx >= n * n - 1)
			break;
		int value = board[load[i].first][load[i].second];
		if (value == 0)
			break;

		for (int j = i + 1; j < load.size(); ++j)
		{
			if (board[load[j].first][load[j].second] != value)
			{
				int dist = j - i;
				cboard[load[idx].first][load[idx].second] = dist;
				idx++;
				cboard[load[idx].first][load[idx].second] = value;
				idx++;
				i = j;

				break;
			}
		}
	}

	for (int i = 0; i < load.size(); ++i)
	{
		board[load[i].first][load[i].second] = cboard[load[i].first][load[i].second];
	}
}

void solve()
{
	cin >> n >> m;
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	visited = vector<vector<bool>>(n + 1, vector<bool>(n + 1));

	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			cin >> board[y][x];
		}
	}

	// load 채워주기
	pair<int, int> pos = { 1, 1 };
	int dy2[] = { 0, 1, 0, -1 };
	int dx2[] = { 1, 0, -1, 0 };
	int dir = 0;
	load.push_back(pos);
	visited[pos.first][pos.second] = true;
	while (true)
	{
		int ny = pos.first + dy2[dir];
		int nx = pos.second + dx2[dir];
		if (ny == (n + 1) / 2 && nx == (n + 1) / 2)
			break;

		if (can_go(ny, nx))
		{
			pos.first = ny;
			pos.second = nx;
			load.push_back({ pos.first, pos.second });
			visited[pos.first][pos.second] = true;
		}
		else
		{
			dir = (dir + 1) % 4;
		}
	}

	reverse(load.begin(), load.end());

	for (int i = 1; i <= m; ++i)
	{
		cin >> d >> s;
		blizard();
		move();

		while (true)
		{
			if (boom())
				move();
			else
				break;
		}

		change();
	}

	cout << ans;
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}

Twitter Facebook LinkedIn

BOJ 21611. 마법사 상어와 블리자드

🙇‍♀️[Gold I] 마법사 상어와 블리자드 - 21611

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀코드

공유하기

참고

BOJ 1436. 영화감독 숌

배열 회전

Split 구현

최대공약수 최소공배수