<Baekjoon> #20056 마법사 상어와 파이어볼 c++

#20056 마법사 상어와 파이어볼
참고1

1. init

• 먼저 Fireball에 저장되는 값이 많기 때문에 구조체를 이용한다

 typedef struct Fireball {
	int y, x;
	int massive;
	int speed;
	int direction;
};
vector <Fireball> fireball;

2. map의 한 칸에 여러개의 fireball이 저장될 수 있기 때문에 한 칸에 여러개의 fireball이 저장될 수 있게 만들어 준다

vector <Fireball> map[MAX][MAX];

3. 각 방향을 지정해주고 홀수, 짝수인 경우의 수도 지정해준다 (마지막에 합쳐지는 fireball의 방향을 정할 때 사용하기 위해)
   

int dy[8] = { -1, -1, 0, 1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int o_dir[4] = { 1,3,5,7 };
int e_dir[4] = {0,2,4,6 };

2. input fireball data

• fireball에 값을 저장할 때 map에서 해당 위치 (r,c)에도 fireball을 저장해준다

void input() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		fireball.push_back({ r, c, m, s,d });
		map[r][c].push_back({ r,c,m,s,d });
	}
}

3. move Fireball

문제에서 이 부분을 살펴 보면 move를 할 때 map밖으로 나가지 않는다는 것을 알 수 있다. 즉 옆으로 이동할 때 (2번 방향) map[0][N-1] 다음은 map[0][0]이 된다는 의미이다

		int move = speed % N;
		int nx_y = y + dy[dir] * move;
		int nx_x = x + dx[dir] * move;
		if (nx_y < 1) nx_y += N;
		if (nx_x < 1) nx_x += N;
		if (nx_y > N) nx_y -= N;
		if (nx_x > N) nx_x -= N;

• map상에서 이동하는 위치에 fireball 저장
• fireball 의 위치는 이동하는 위치로 바꾸어줌

		map[nx_y][nx_x].push_back({ nx_y, nx_x, mass, speed, dir });
		fireball[i].y = nx_y;
		fireball[i].x = nx_x;

4. sum fireball

• 먼저 임시로 fireball을 저장할 tmp 생성

vector<Fireball> tmp;

• map 상의 모든 좌표를 돌면서 해당 지점에 한 개의 fireball이 있을 경우 그냥 tmp에 저장하고 두 개 이상의 fireball이 있을 경우 합쳐지는 연산을 수행
• 모든 방향이 짝수이거나 홀수인 경우에는 {0,2,4,6}으로 그렇지 않으면 {1,3,5,7} 로 이동해야 하므로 모든 방향이 같은 방향인지 검사해야한다

먼저 even, odd를 true로 초기화 해두고

bool even = true;
bool odd = true;

어떤 방향이든 한 번 나오면 false로 바꾸어준다

if (map[i][j][k].direction % 2 == 0) odd = false; 
else even = false;

만약 둘 중 하나가 true라는 말은 모두 같은 방향에 나왔다는 뜻이므로 처음에 만들어 두었던
int o_dir[4] = { 1,3,5,7 };
int e_dir[4] = {0,2,4,6 };
을 이용해 각 방향으로 흩어지게 한다

if (even == true || odd == true)
	for (int m = 0; m < 4; m++)
		tmp.push_back({ i, j, mass, speed, e_dir[m] });
else
	for (int m = 0; m < 4; m++)
		tmp.push_back({ i,j,mass,speed, o_dir[m] });

• 마지막에 tmp 에 있던 fireball들을 fireball 로 이동

fireball = tmp;

전체코드

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 51;
int N, M, K;

 typedef struct Fireball {
	int y, x;
	int massive;
	int speed;
	int direction;
};

int dy[8] = { -1, -1, 0, 1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int o_dir[4] = { 1,3,5,7 };
int e_dir[4] = {0,2,4,6 };

vector <Fireball> fireball;
vector <Fireball> map[MAX][MAX];

void input() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		fireball.push_back({ r, c, m, s,d });
		map[r][c].push_back({ r,c,m,s,d });
	}
}

void moveFireball() {
	memset(map, 0, sizeof(map));

	for (int i = 0; i < fireball.size(); i++) {
		int y = fireball[i].y;
		int x = fireball[i].x;
		int mass = fireball[i].massive;
		int speed = fireball[i].speed;
		int dir = fireball[i].direction;

		int move = speed % N;
		int nx_y = y + dy[dir] * move;
		int nx_x = x + dx[dir] * move;
		if (nx_y < 1) nx_y += N;
		if (nx_x < 1) nx_x += N;
		if (nx_y > N) nx_y -= N;
		if (nx_x > N) nx_x -= N;

		map[nx_y][nx_x].push_back({ nx_y, nx_x, mass, speed, dir });
		fireball[i].y = nx_y;
		fireball[i].x = nx_x;
	}
}

void sumFireball() {
	vector<Fireball> tmp;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j].size() == 0) continue;
			if (map[i][j].size() == 1) {
				tmp.push_back(map[i][j][0]);
				continue;
			}

			bool even = true;
			bool odd = true;

			int mass_sum = 0;
			int speed_sum = 0;
			int mapSize = map[i][j].size();

			for (int k = 0; k < mapSize; k++) {
				mass_sum += map[i][j][k].massive;
				speed_sum += map[i][j][k].speed;
				if (map[i][j][k].direction % 2 == 0) odd = false; 
				else even = false;
			}
			int mass = mass_sum / 5;
			int speed = speed_sum / mapSize;

			if (mass == 0) continue;
			if (even == true || odd == true)
				for (int m = 0; m < 4; m++)
					tmp.push_back({ i, j, mass, speed, e_dir[m] });
			else
				for (int m = 0; m < 4; m++)
					tmp.push_back({ i,j,mass,speed, o_dir[m] });
		}
		fireball = tmp;
	}
}

void solution() {
	for (int i = 0; i < K; i++) {
		moveFireball();
		sumFireball();
	}
	int answer = 0;
	for (int i = 0; i < fireball.size(); i++)
		answer += fireball[i].massive;

	cout << answer << endl;
}

int main() {
	input();
	solution();
	return 0;
}