[백준 20056번 - 마법사 상어와 파이어볼] C++ 풀이

20056번.

 

'1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다'

이 말인 즉슨, 1행에서 범위 초과하여 0행으로 갔을때, N행에 놓아주고, 1열에서 범위를 초과하여 0열로 갔을 때 N열에 놓아라는 의미이다. 반대로, N행에 있다가 범위를 초과하여 N + 1행으로 가면, 다시 1행에 놓아준다. 

 

로직은 문제에 쓰인 그대로 풀이해주면 된다.

나는 2차원 벡터에 파이어볼을 담고있는 큐를 담았다.

그리고 이동한 파이어볼을 new_map 에 담아주고, 검사하면서 2개 이상 파이어볼이 있으면 합친 다음 4개로 만들어 주었다. 이 때, 만약 질량이 0이라면 파이어볼을 없애준다.

 

k 번 이동 후에 남아있는 파이어볼 질량 총 합을 구해주면 된다.

 

#include <stdio.h>
#include <vector>
#include <queue>

#define MAX 51

using namespace std;

struct fireball {
	int r;
	int c;
	int m; // 질량
	int d; // 방향
	int s; // 속력
};

int n, m, p;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int ans = 0;

int main() {
	scanf("%d %d %d", &n, &m, &p);
	vector<vector<queue<fireball>>> map;
	vector<vector<queue<fireball>>> new_map;

	map.assign(n + 1, vector<queue<fireball>>(n + 1));
	new_map.assign(n + 1, vector<queue<fireball>>(n + 1));

	for(int i = 0; i < m; ++i) {
		fireball tmp;
		scanf("%d %d %d %d %d", &tmp.r, &tmp.c, &tmp.m, &tmp.s, &tmp.d);
		map[tmp.r][tmp.c].push(tmp);
	}

	for(int i = 0; i < p; ++i) {
		// 파이어볼 이동
		for(int j = 1; j <= n; ++j) {
			for(int k = 1; k <= n; ++k) {
				if (!map[j][k].empty()) {
					int size = map[j][k].size();
					for(int v = 0; v < size; ++v) {
						int x = map[j][k].front().r;
						int y = map[j][k].front().c;
						// d방향으로 s번 만큼 이동
						for(int u = 0; u < map[j][k].front().s; ++u) {
							x = x + dx[map[j][k].front().d];
							y = y + dy[map[j][k].front().d];
							if (x > n)
								x = 1;
							if (y > n)
								y = 1;
							if (x < 1)
								x = n;
							if (y < 1)
								y = n;
						}
						fireball tmp = map[j][k].front();
						tmp.r = x;
						tmp.c = y;
						new_map[x][y].push(tmp);
						map[j][k].pop();
					}
				}
			}
		}

		// 2개 이상의 파이어볼이 있는 칸이 있다면
		for(int j = 1; j <= n; ++j) {
			for(int k = 1; k <= n; ++k) {
				if (new_map[j][k].size() == 1) {
					map[j][k] = new_map[j][k];
					new_map[j][k].pop();
				} else if (new_map[j][k].size() >= 2) {
					// 같은 칸의 파이어볼을 하나로 합친다
					int m_sum = 0;
					int s_sum = 0;
					int size = new_map[j][k].size();
					bool isAllEven = false;
					bool isAllOdd = false;
					while(!new_map[j][k].empty()) {
						m_sum += new_map[j][k].front().m;
						s_sum += new_map[j][k].front().s;
						if (new_map[j][k].front().d % 2 == 0) {
							isAllEven = true;
						} else {
							isAllOdd = true;
						}
						new_map[j][k].pop();
					}
					// 파이어볼은 4개의 파이어볼로 나눈다.
					// 나누어진 파이어볼의 질량은 1/5
					// 속력은 속력합 / 합쳐진 파이어볼 갯수
					// 합쳐지는 파이어볼의 방향이 모두 홀수 or 모두 짝수면 0, 2, 4, 6 아니면 1, 3, 5, 7
					if (isAllEven == isAllOdd && m_sum / 5 > 0) {
						for(int u = 0; u < 4; ++u) {
							fireball fb;
							fb.r = j;
							fb.c = k;
							fb.s = s_sum / size;
							fb.d = u * 2 + 1;
							fb.m = m_sum / 5;
							map[j][k].push(fb);
						}
					} else if (isAllEven != isAllOdd && m_sum / 5 > 0) {
						for(int u = 0; u < 4; ++u) {
							fireball fb;
							fb.r = j;
							fb.c = k;
							fb.s = s_sum / size;
							fb.d = u * 2;
							fb.m = m_sum / 5;
							map[j][k].push(fb);
						}
					}
				}
			}
		}

	}

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if (map[i][j].size() > 0) {
				while(!map[i][j].empty()) {
					ans += map[i][j].front().m;
					map[i][j].pop();
				}
			}
		}
	}

	printf("%d\n", ans);
}