[백준] 마법사 상어와 파이어볼

문제 설명

https://www.acmicpc.net/problem/20056

제한사항

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

---

풀이

75분
잘한 점: 풀이를 끝까지 생각해낼 때 까지 키보드를 잡지 않았다.
못한 점: 문제에서 파이어볼이 사라지는(즉, 질량이 0이 되는) 경우를 제외하려고 조건문에 탈출문을 쓰는 실수를 했다. 탈출문을 써서 해당 행의 나머지 공간은 탐색하지 못하는 오류가 발생했다.

if ((int)(m_sum / 5) == 0) continue;

코드

// 04:04 ~ 05:19
//#pragma warning (disable:4996)
#include<iostream>
#include<vector>
using namespace std;

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

struct fireball {
	int x, y, m, s, dir;
};

int main()
{
	// freopen("input.txt", "r", stdin);
	int n, m, k;
	int visit[50][50] = { 0, };
	int sum = 0;
	vector<fireball> now;
	vector<fireball> next;

	cin >> n >> m >> k;
	for (int i = 0; i < m; ++i) {
		fireball temp;
		cin >> temp.x >> temp.y >> temp.m >> temp.s >> temp.dir;
		--temp.x;
		--temp.y;
		now.push_back(temp);
	}

	while (k > 0) {

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				visit[i][j] = 0;
			}
		}

		for (int i = 0; i < now.size(); ++i) {
			now[i].x = (now[i].x + 1000 * n + now[i].s * dx[now[i].dir]) % n;
			now[i].y = (now[i].y + 1000 * n + now[i].s * dy[now[i].dir]) % n;
			visit[now[i].x][now[i].y]++;
		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (visit[i][j] >= 2) {
					int m_sum = 0;
					vector<int> dirs;
					int s_sum = 0;
					for (int k = 0; k < now.size(); ++k) {
						if (now[k].x == i && now[k].y == j) {
							m_sum += now[k].m;
							dirs.push_back(now[k].dir);
							s_sum += now[k].s;
							now.erase(now.begin() + k);
							--k;
						}
					}

					if ((int)(m_sum / 5) == 0) continue;

					fireball temp;
					int d = 0;

					for (int k = 0; k < dirs.size() - 1; ++k) {
						if ((dirs[k] + dirs[k + 1]) % 2 != 0) {
							d = 1;
							break;
						}
					}

					temp.x = i;
					temp.y = j;
					temp.m = m_sum / 5;
					temp.s = s_sum / visit[i][j];

					for (d; d <= 7; d += 2) {
						temp.dir = d;
						next.push_back(temp);
					}
				}
			}
		}

		for (int i = 0; i < next.size(); ++i) {
			now.push_back(next[i]);
		}

		next.clear();
		--k;
	}

	for (int i = 0; i < now.size(); ++i) {
		sum += now[i].m;
	}

	cout << sum;

	return 0;
}