백준 21610 마법사 상어와 비바라기 문제풀이(C++)

YooHeeJoon·2023년 2월 4일
구현백준
0

백준 문제풀이

목록 보기
50/56

백준 21610 마법사 상어와 비바라기

조건 구현

1. 이동 명령 내리기 전

  1. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다.
struct cloud
{
	void location_clearance(const int basket_size)
	{
		y = (y >= basket_size ? y % basket_size : y < 0 ? (basket_size * 30 + y) % basket_size : y);
		x = (x >= basket_size ? x % basket_size : x < 0 ? (basket_size * 30 + x) % basket_size : x);
	}
	int y;
	int x;
};
  1. 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다
void clouds_initialize(vector<cloud>& clouds, const int basket_size)
{
	clouds.push_back({ basket_size - 1, 0 });
	clouds.push_back({ basket_size - 1, 1 });
	clouds.push_back({ basket_size - 2, 0 });
	clouds.push_back({ basket_size - 2, 1 });
}
  1. 이동 명령 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 
// global variable
// 1부터 이기에 moving[0]에 아무값이나 대입
constexpr int moving[9][2] = { {0,0}, {0,-1}, {-1,-1},{-1,0},{-1,1},{0,1},{1, 1},{1,0},{1,-1} };
// ----

2. 이동 명령 내린 후

  1. 모든 구름이 di 방향으로 si칸 이동한다.
void move_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size, const int move_direction, const int move_squares)
{
	for (cloud& cloud : clouds)
	{
		cloud.y += (moving[move_direction][0]) * move_squares;
		cloud.x += (moving[move_direction][1]) * move_squares;
        // 격자의 연결
		cloud.location_clearance(basket_size);
        // 2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
		baskets[cloud.y][cloud.x]++;
        // 구름들의 위치를 담는 배열 5번 조건에서 사용
		clouds_location[cloud.y][cloud.x] = true;
	}
}
  1. 구름이 모두 사라진다.
vector<cloud>().swap(clouds); // free
  1. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
void water_copy_burg(vector<vector<int>>& baskets, const vector<cloud>& clouds, const int basket_size)
{
	// 선행으로 복사되어서 증가한 칸이 다음에 진행할 칸에 영향을 미치지 않게 하기 위한 임시 배열
	vector<vector<int>> copy_baskets(baskets);
	for (const cloud cloud : clouds)
	{
		for (int i = 2; i <= 8; i += 2) // ↖, ↗, ↘, ↙  방향 탐색
		{
			const int y = cloud.y + moving[i][0];
			const int x = cloud.x + moving[i][1];
			if (check_area(basket_size, y, x) || baskets[y][x] == 0)
			{
				continue;
			}
			copy_baskets[cloud.y][cloud.x]++;
		}
	}
	baskets.swap(copy_baskets);
}
// ----- 
// 4-1. 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
bool check_area(const int basket_size, const int y, const int x)
{
	return y < 0 || y >= basket_size || x < 0 || x >= basket_size;
}
  1. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
void make_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size)
{
	for (int i = 0; i < basket_size; i++)
	{
		for (int j = 0; j < basket_size; j++)
		{
        	// 3에서 구름이 사라진 칸이 아니어야 한다.
			if (clouds_location[i][j])
			{
				clouds_location[i][j] = false;
				continue;
			}
            // 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
			if (baskets[i][j] > 1)
			{
				clouds.push_back({ i, j });
				baskets[i][j] -= 2;
				clouds_location[i][j] = true;
			}
		}
	}
}
  1. 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
int print_water_sum(const vector<vector<int>>& baskets, const int basket_size)
{
	int sum = 0;
	for (int i = 0; i < basket_size; i++)
	{
		for (int j = 0; j < basket_size; j++)
		{
			sum += baskets[i][j];
		}
	}
	return sum;
}

각각 구현한 조건들을 순서에 맞게 조합한다!

정답 코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
constexpr int moving[9][2] = { {0,0}, {0,-1}, {-1,-1},{-1,0},{-1,1},{0,1},{1, 1},{1,0},{1,-1} };
struct cloud
{
	void location_clearance(const int basket_size)
	{
		y = (y >= basket_size ? y % basket_size : y < 0 ? (basket_size * 30 + y) % basket_size : y);
		x = (x >= basket_size ? x % basket_size : x < 0 ? (basket_size * 30 + x) % basket_size : x);
	}
	int y;
	int x;
};

void clouds_initialize(vector<cloud>& clouds, const int basket_size)
{
	clouds.push_back({ basket_size - 1, 0 });
	clouds.push_back({ basket_size - 1, 1 });
	clouds.push_back({ basket_size - 2, 0 });
	clouds.push_back({ basket_size - 2, 1 });
}

bool check_area(const int basket_size, const int y, const int x)
{
	return y < 0 || y >= basket_size || x < 0 || x >= basket_size;
}

void make_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size)
{
	for (int i = 0; i < basket_size; i++)
	{
		for (int j = 0; j < basket_size; j++)
		{
			if (clouds_location[i][j])
			{
				clouds_location[i][j] = false;
				continue;
			}
			if (baskets[i][j] > 1)
			{
				clouds.push_back({ i, j });
				baskets[i][j] -= 2;
				clouds_location[i][j] = true;
			}
		}
	}
}

void water_copy_burg(vector<vector<int>>& baskets, const vector<cloud>& clouds, const int basket_size)
{
	vector<vector<int>> copy_baskets(baskets);
	for (const cloud cloud : clouds)
	{
		for (int i = 2; i <= 8; i += 2)
		{
			const int y = cloud.y + moving[i][0];
			const int x = cloud.x + moving[i][1];
			if (check_area(basket_size, y, x) || baskets[y][x] == 0)
			{
				continue;
			}
			copy_baskets[cloud.y][cloud.x]++;
		}
	}
	baskets.swap(copy_baskets);
}

void move_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size, const int move_direction, const int move_squares)
{
	for (cloud& cloud : clouds)
	{
		cloud.y += (moving[move_direction][0]) * move_squares;
		cloud.x += (moving[move_direction][1]) * move_squares;
		cloud.location_clearance(basket_size);
		baskets[cloud.y][cloud.x]++;
		clouds_location[cloud.y][cloud.x] = true;
	}
}

void wising_rain(vector<vector<int>>& baskets, const int basket_size, int move_command_size)
{
	vector<cloud> clouds;
	clouds_initialize(clouds, basket_size);
	while (move_command_size--)
	{
		vector<vector<bool>> clouds_location(basket_size, vector<bool>(basket_size));
		int move_direction, move_squares;
		cin >> move_direction >> move_squares;

		move_clouds(baskets, clouds, clouds_location, basket_size, move_direction, move_squares);
		water_copy_burg(baskets, clouds, basket_size);
		vector<cloud>().swap(clouds); // free
		make_clouds(baskets, clouds, clouds_location, basket_size);
	}
}

int print_water_sum(const vector<vector<int>>& baskets, const int basket_size)
{
	int sum = 0;
	for (int i = 0; i < basket_size; i++)
	{
		for (int j = 0; j < basket_size; j++)
		{
			sum += baskets[i][j];
		}
	}
	return sum;
}

int main() {
	FAST_IO;
	int basket_size, move_command_size;
	cin >> basket_size >> move_command_size;
	vector<vector<int>> baskets(basket_size, vector<int>(basket_size));
	for (int i = 0; i < basket_size; i++)
	{
		for (int j = 0; j < basket_size; j++)
		{
			cin >> baskets[i][j];
		}
	}
	wising_rain(baskets, basket_size, move_command_size);
	cout << print_water_sum(baskets, basket_size) << '\n';
	return 0;
}

profile
YooHeeJoon
이전 포스트

백준 16719번 ZOAC 문제풀이(C++)

다음 포스트

백준 20056번 마법사 상어와 파이어볼 문제풀이(C++)

0개의 댓글