BOJ 21610. 마법사 상어와 비바라기

24-03-16

🙇‍♀️[Gold V] 마법사 상어와 비바라기 - 21610

문제 링크

성능 요약

메모리: 2156 KB, 시간: 96 ms

분류

구현, 시뮬레이션

제출 일자

2024년 3월 16일 14:54:25

문제 설명

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 d_i과 거리 s_i로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

모든 구름이 d_i 방향으로 s_i칸 이동한다.
각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
구름이 모두 사라진다.
2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
- 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
- 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 d_i, s_i가 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

🚀풀이

1, 1부터 좌표가 시작하므로 n을 넘었을 경우, 0이 됐을 경우를 생각해서 move_cloud 함수를 만들어야한다.

나의 경우 n을 더하고 다시 n으로 나눈 나머지를 구해서 n을 넘긴 경우를 처리했고, 0이 되는 경우에는 그냥 n으로 대입해서 해결했다.

void move_cloud()
{
	for (int i = 0; i < clouds.size(); ++i)
	{
		for (int j = 0; j < s; ++j)
		{
			int ny = (clouds[i].first + dy[d - 1] + n) % n;
			if (ny == 0)
				ny = n;
			clouds[i].first = ny;
			int nx = (clouds[i].second + dx[d - 1] + n) % n;
			if (nx == 0)
				nx = n;
			clouds[i].second = nx;
		}
	}
}

그 다음 물 주기는 그냥 물주면 됨.

void add_water()
{
	for (int i = 0; i < clouds.size(); ++i)
	{
		board[clouds[i].first][clouds[i].second]++;
	}
}

구름을 제거하는 것은 원래 구름을 다 지우면 안된다.

구름이 있었던 자리에 구름을 생성하면 안되므로 remove_clouds에 저장했다가 지웠다.

void remove_cloud()
{
	remove_clouds.clear();

	for (int i = 0; i < clouds.size(); ++i)
	{
		remove_clouds.push_back({ clouds[i].first, clouds[i].second });
	}

	clouds.clear();
}

물 복사 마법을 시전하는데 여기서 remove_clouds의 구름들로 구하면된다.

void clone_water()
{
	for (int i = 0; i < remove_clouds.size(); ++i)
	{
		int cnt = 0;
		for (int j = 0; j < 4; ++j)
		{
			int ny = remove_clouds[i].first + diaY[j];
			int nx = remove_clouds[i].second + diaX[j];

			if (ny < 1 || nx < 1 || ny > n || nx > n)
				continue;
			if (board[ny][nx] == 0)
				continue;

			cnt++;
		}

		board[remove_clouds[i].first][remove_clouds[i].second] += cnt;
	}
}

구름을 생성하고 물을 줄이는 부분은 remove_clouds와 같은 좌표가 있으면 계산하면 안된다.

void create_cloud()
{
	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			if (board[y][x] < 2)
				continue;
			// 사라졌던 구름자리에 구름이 생기면 안됨.
			bool flag = true;
			for (int i = 0; i < remove_clouds.size(); ++i)
			{
				if (y == remove_clouds[i].first && x == remove_clouds[i].second)
				{
					flag = false;
					break;
				}
			}

			if (flag == true)
			{
				board[y][x] -= 2;
				clouds.push_back({ y, x });
			}
		}
	}

	remove_clouds.clear();
}

3중 for문으로 비효율적인 코드인데 n이 50까지고 m도 50까지여서 시간 복잡도가 충분할거같다고 판단했다.

solve함수는 다음과 같다.

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

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

	// 비바라기 마법 시전
	clouds.push_back({ n, 1 });
	clouds.push_back({ n, 2 });
	clouds.push_back({ n - 1, 1 });
	clouds.push_back({ n - 1, 2 });

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

		// 구름이 이동한다.
		move_cloud();

		// 물이 1 증가한다. 
		add_water();

		// 구름이 사라진다.
		remove_cloud();

		// 물 복사 마법이 시전된다.
		clone_water();

		// 구름이 생성되고 물이 양이 2 줄어든다.
		create_cloud();
	}

	int ret = 0;

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

	cout << ret;
}

끝!

🚀코드

#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;
int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int diaY[] = { -1, -1, 1, 1 };
int diaX[] = { -1, 1, 1, -1 };
vector<vector<int>> board;
vector<pair<int, int>> clouds;
vector<pair<int, int>> remove_clouds;

void move_cloud()
{
	for (int i = 0; i < clouds.size(); ++i)
	{
		for (int j = 0; j < s; ++j)
		{
			int ny = (clouds[i].first + dy[d - 1] + n) % n;
			if (ny == 0)
				ny = n;
			clouds[i].first = ny;
			int nx = (clouds[i].second + dx[d - 1] + n) % n;
			if (nx == 0)
				nx = n;
			clouds[i].second = nx;
		}
	}
}

void add_water()
{
	for (int i = 0; i < clouds.size(); ++i)
	{
		board[clouds[i].first][clouds[i].second]++;
	}
}

void remove_cloud()
{
	remove_clouds.clear();

	for (int i = 0; i < clouds.size(); ++i)
	{
		remove_clouds.push_back({ clouds[i].first, clouds[i].second });
	}

	clouds.clear();
}

void clone_water()
{
	for (int i = 0; i < remove_clouds.size(); ++i)
	{
		int cnt = 0;
		for (int j = 0; j < 4; ++j)
		{
			int ny = remove_clouds[i].first + diaY[j];
			int nx = remove_clouds[i].second + diaX[j];

			if (ny < 1 || nx < 1 || ny > n || nx > n)
				continue;
			if (board[ny][nx] == 0)
				continue;

			cnt++;
		}

		board[remove_clouds[i].first][remove_clouds[i].second] += cnt;
	}
}

void create_cloud()
{
	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			if (board[y][x] < 2)
				continue;
			// 사라졌던 구름자리에 구름이 생기면 안됨.
			bool flag = true;
			for (int i = 0; i < remove_clouds.size(); ++i)
			{
				if (y == remove_clouds[i].first && x == remove_clouds[i].second)
				{
					flag = false;
					break;
				}
			}

			if (flag == true)
			{
				board[y][x] -= 2;
				clouds.push_back({ y, x });
			}
		}
	}

	remove_clouds.clear();
}

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

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

	// 비바라기 마법 시전
	clouds.push_back({ n, 1 });
	clouds.push_back({ n, 2 });
	clouds.push_back({ n - 1, 1 });
	clouds.push_back({ n - 1, 2 });

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

		// 구름이 이동한다.
		move_cloud();

		// 물이 1 증가한다. 
		add_water();

		// 구름이 사라진다.
		remove_cloud();

		// 물 복사 마법이 시전된다.
		clone_water();

		// 구름이 생성되고 물이 양이 2 줄어든다.
		create_cloud();
	}

	int ret = 0;

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

	cout << ret;
}

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 21610. 마법사 상어와 비바라기

🙇‍♀️[Gold V] 마법사 상어와 비바라기 - 21610

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀코드

공유하기

참고

BOJ 14620. 꽃길

BOJ 13301. 타일 장식물

BOJ 13301. 타일 장식물

BOJ 9934. 완전 이진 트리