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

백준 20056번 마법사 상어와 파이어볼

아이디어

파이어볼의 정보와 합쳐졌을 때의 정보들을 담을 구조체

// 파이어볼 정보
struct fireball
{
// 위치 조정
	void location_clearance(const int grid_size)
	{
		r = r % grid_size;
		r = r < 0 ? r + grid_size : r;
		c = c % grid_size;
		c = c < 0 ? c + grid_size : c;
	}
	int r;
	int c;
	int m;
	int s;
	int d;
};
struct merged_contents
{
	merged_contents() : count(0), m(0), s(0) {}
    // 방향이 다 짝수이거나 홀수 인지 판별
	bool odd_even() const
	{
		bool flag = true;
		for (int i = 1; i < static_cast<int>(d.size()); i++)
		{
			(d[0] & 1) == (d[i] & 1) ? flag : flag = false;
		}
		return flag;
	}
	int count;
	int m;
	int s;
	vector<int> d;
};
// 사용할 자료 선언
typedef map<int, merged_contents> merged_fireball;

조건 (이동 전)

1.모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다
※이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.

void move(vector<fireball>& fireballs, const int grid_size)
{
	for (fireball& fireball : fireballs) 
	{
		fireball.r += move_way[fireball.d][0] * fireball.s;
		fireball.c += move_way[fireball.d][1] * fireball.s;
		fireball.location_clearance(grid_size);
	}
}

조건 (이동 후)

1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.

merged_fireball merged_fireballs(const vector<fireball>& fireballs)
{
	merged_fireball merged;
	for (const fireball fireball : fireballs)
	{
		const int location = fireball.r * 100 + fireball.c;
		merged[location].count++;
		merged[location].m += fireball.m;
		merged[location].s += fireball.s;
		merged[location].d.push_back(fireball.d);
	}
	return merged;
}

2, 3, 4번 조건

void divide_4_fireballs(vector<fireball>& fireballs, const merged_fireball& merged)
{
	for (auto fireball : merged)
	{
		const int r = fireball.first / 100;
		const int c = fireball.first % 100;
        // 3 - 1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
		const int mass = fireball.second.m / 5;
        // 3 - 2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
		const int speed = fireball.second.s / fireball.second.count;
		if (fireball.second.count == 1)
		{
			fireballs.push_back({ r, c, fireball.second.m, fireball.second.s, fireball.second.d[0] });
			continue;
		}
        // 4. 질량이 0인 파이어볼은 소멸되어 없어진다.
		if (!mass) {
			continue;
		}
		int idx = 1;
        // 3 - 3 . 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
		if (fireball.second.odd_even())
		{
			idx = 0;
		}
		for (; idx < 8; idx += 2) // 2. 파이어볼은 4개의 파이어볼로 나누어진다.
			fireballs.push_back({ r, c, mass, speed, idx });
	}
}

정답코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
constexpr int move_way[8][2] = { {-1, 0}, {-1,1}, {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
struct fireball
{
	void location_clearance(const int grid_size)
	{
		r = r % grid_size;
		r = r < 0 ? r + grid_size : r;
		c = c % grid_size;
		c = c < 0 ? c + grid_size : c;
	}
	int r;
	int c;
	int m;
	int s;
	int d;
};
struct merged_contents
{
	merged_contents() : count(0), m(0), s(0) {}
	bool odd_even() const
	{
		bool flag = true;
		for (int i = 1; i < static_cast<int>(d.size()); i++)
		{
			(d[0] & 1) == (d[i] & 1) ? flag : flag = false;
		}
		return flag;
	}
	int count;
	int m;
	int s;
	vector<int> d;
};
typedef map<int, merged_contents> merged_fireball;
void move(vector<fireball>& fireballs, const int grid_size)
{
	for (fireball& fireball : fireballs)
	{
		fireball.r += move_way[fireball.d][0] * fireball.s;
		fireball.c += move_way[fireball.d][1] * fireball.s;
		fireball.location_clearance(grid_size);
	}
}
merged_fireball merged_fireballs(const vector<fireball>& fireballs)
{
	merged_fireball merged;
	for (const fireball fireball : fireballs)
	{
		const int location = fireball.r * 100 + fireball.c;
		merged[location].count++;
		merged[location].m += fireball.m;
		merged[location].s += fireball.s;
		merged[location].d.push_back(fireball.d);
	}
	return merged;
}
void divide_4_fireballs(vector<fireball>& fireballs, const merged_fireball& merged)
{
	for (auto fireball : merged)
	{
		const int r = fireball.first / 100;
		const int c = fireball.first % 100;
		const int mass = fireball.second.m / 5;
		const int speed = fireball.second.s / fireball.second.count;
		if (fireball.second.count == 1)
		{
			fireballs.push_back({ r, c, fireball.second.m, fireball.second.s, fireball.second.d[0] });
			continue;
		}
		if (!mass) {
			continue;
		}
		int idx = 1;
		if (fireball.second.odd_even())
		{
			idx = 0;
		}

		for (; idx < 8; idx += 2)
			fireballs.push_back({ r, c, mass, speed, idx });
	}
}
void print_mass_sum(const vector<fireball>& fireballs)
{
	int mass_sum = 0;
	for (const fireball fireball : fireballs)
	{
		mass_sum += fireball.m;
	}
	cout << mass_sum << '\n';
}
void command(vector<fireball>& fireballs, const int grid_size)
{
	move(fireballs, grid_size);
	const merged_fireball merged = merged_fireballs(fireballs);
	vector<fireball>().swap(fireballs); // free
	divide_4_fireballs(fireballs, merged);
}
int main()
{
	FAST_IO;
	int n, m, k; cin >> n >> m >> k;
	vector<fireball> fireballs(m);
	for (fireball& fireball : fireballs)
	{
		cin >> fireball.r >> fireball.c >> fireball.m >> fireball.s >> fireball.d;
	}
	while (k--)
	{
		command(fireballs, n);
	}
	print_mass_sum(fireballs);
	return 0;
}