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

일단 통과했는데, 442ms걸렸다;
딱 봐도 queue로 구현하면서 쓸모없이 push, pop하는 것이 많아서 그런 것 같은데, deque로 다시 구현해보려고 한다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, m, k;
int r, c, measure, speed, dir;
int ballinfo[3000][5];
int rowDir[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int colDir[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef struct __ball {
	int measure;
	int speed;
	int dir;
	int iter;
} ball;
queue<ball> map[50][50];
void print_map(const char *s) 
{
	printf("%s\n", s);
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			if (map[row][col].empty())
				continue;
			printf("[%d][%d]'s Size(%d) : ", row, col, map[row][col].size());
			if (map[row][col].empty()) 
				printf("[Empty]");
			queue<ball>& q = map[row][col];
			int size = q.size();
			int cnt = 0;
			while (1) {
				if (cnt == size)
					break;
				ball b = q.front(); q.pop();
				printf("[%d %d %d %d] ", b.measure, b.speed, b.dir, b.iter);
				q.push(b);
				cnt++;
			}
			printf("\n");
		}
	}
}
void move_ball(int iter)
{
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			queue<ball> &q = map[row][col];
			int cnt = 0;
			int size = q.size();
			while (1) {
				if (q.empty())
					break;
				if (cnt == size)
					break;
				ball b = q.front();
				cnt++;
				if (b.iter != iter)
					continue;
				q.pop();
				int nrow = row;
				int ncol = col;
				for (int j = 0; j < b.speed; j++) {
					nrow = nrow + rowDir[b.dir];
					ncol = ncol + colDir[b.dir];
					nrow = nrow < 0 ? n - 1 : nrow;
					ncol = ncol < 0 ? n - 1 : ncol;
					nrow = nrow > n - 1 ? 0 : nrow;
					ncol = ncol > n - 1 ? 0 : ncol;
				}
				map[nrow][ncol].push({ b.measure, b.speed, b.dir, b.iter + 1 });
			}
		}
	}
}
void merge_ball(int iter)
{
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			queue<ball>& q = map[row][col];
			int size = q.size();
			if (size < 2)
				continue;
			
			ball first = q.front(); q.pop();
			int total_measure = first.measure;
			int total_speed = first.speed;
			bool all_dir_same = true;
			bool is_odd = (first.dir & 1) ? true : false;
			while (1) {
				if (q.empty())
					break;
				ball b = q.front(); q.pop();
				total_measure += b.measure;
				total_speed += b.speed;
				if (is_odd && ((b.dir & 1) == 0))
					all_dir_same = false;
				if (!is_odd && ((b.dir & 1) == 1))
					all_dir_same = false;
			}
			int new_measure = (int)(total_measure / 5);
			if (new_measure == 0)
				continue;
			int new_dir = all_dir_same ? 0 : 1;
			int new_speed = (int)(total_speed / size);
			for (int i = 0; i < 4; i++) {
				ball b = { new_measure, new_speed, new_dir, iter + 1 };
				q.push(b);
				new_dir += 2;
			}
		}
	}
}
int answer = 0;
void get_answer()
{
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			queue<ball>& q = map[row][col];
			if (q.empty())
				continue;
			int size = q.size();
			int cnt = 0;
			while (1) {
				if (cnt == size)
					break;
				ball b = q.front(); q.pop();
				answer += b.measure;
				q.push(b);
				cnt++;
			}
		}
	}
}
void solve(int iter)
{
	//print_map("Before Move Ball");

	move_ball(iter);

	//print_map("Before Merge Ball");

	merge_ball(iter);

	//print_map("After Process");
}
int main(void)
{
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> r >> c >> measure >> speed >> dir;
		ball b = { measure, speed, dir, 0 };
		map[r-1][c-1].push(b);
	}
	for (int iter = 0; iter < k; iter++) {
		//printf("Iteration Start [%d]\n", iter);
		solve(iter);
		//printf("\n");
	}
	get_answer();
	cout << answer << "\n";
	return 0;
}