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

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

20056번: 마법사 상어와 파이어볼

 

- 시뮬레이션 + 구현 문제이다. 시간복잡도는 k번 이동 * 각 이동마다 m개의 파이어볼이 이동하므로 O(km)이다.

 

- 필자는 모든 정보를 vector 하나로 해결했다. vector에 들어가는 요소들은 순서대로 질량, 속력, 방향, 이동 여부이다. 

 

- 가장 먼저, 파이어볼의 정보를 받아 push_back한다. 이 후, 총 k번의 이동을 진행한다.

 

1. 파이어볼이 자신의 방향과 속력을 활용하여 다음 칸으로 이동한다. 이 때, 속력만큼 for문을 통해 한 칸씩 이동을 하는데, 1번 행(열)0과 n번 행(열)이 연결되어 있으므로, 이를 잘 활용하여 이동 중 1과 n 사이를 벗어나는 경우를 잘 처리 해 준다. 이 후, 파이어볼이 이동을 마치면 기존 좌표의 파이어볼을 erase 해 주고, 새로운 좌표에 해당 파이어볼을 push_back 한다. 이렇게 이동해야 하는 파이어볼들이 모두 이동을 했다면 while문을 빠져나오게 된다. 이 과정에서, 해당 좌표에서 존재하던 파이어볼들이 모두 이동해야 했던 상황이라면(즉, second.second가 false) while 조건 체크에서 오류가 날 수 있으므로 해당 좌표가 비었을 때 break를 해 주도록 조건을 추가 해 준다.

 

2. 다음으로, 모든 파이어볼들의 이동여부를 false로 초기화 해 준다.(다음 이동을 위해)

 

3. 이제 하나의 area에 2개 이상의 파이어볼이 존재하는지를 체크 한다. 2개 이상이 존재한다면, 주어진 조건대로 질량과 속력, 방향을 계산해서 새로 해당 area에 push를 하면 된다.

 

- 1시간 10분정도가 걸린 문제이다. 이유는 변수를 잘못 입력받고, 2번 과정을 빼먹어서.. ㅜㅜ 그래도 구현 능력이 많이 늘었다는 것에 의의를 둔다.

#include <iostream>
#include <vector>
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1,1,1,0,-1,-1,-1 };
int n, m, k;
using namespace std;
vector<pair<pair<int, int>, pair<int, bool>>> v[51][51];
void debugging() {
	for (int i = 1; i <= n; i++) { // 자신의 칸으로 이동
		for (int j = 1; j <= n; j++) {
			cout << v[i][j].size() << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int r, c, m, d, s;
		cin >> r >> c >> m >> s >> d;
		v[r][c].push_back({{ m,s }, { d,false }});
	}
	while (k--) {
		for (int i = 1; i <= n; i++) { // 자신의 칸으로 이동
			for (int j = 1; j <= n; j++) {
				if (v[i][j].empty()) continue;
				while (v[i][j][0].second.second == false) { // 아직 이동을 안 한 파이어볼이라면
					int s = v[i][j][0].first.second; int m = v[i][j][0].first.first; int d = v[i][j][0].second.first;
					int nx = i; int ny = j;
					for (int k = 0; k < s; k++) {
						nx += dx[d]; ny += dy[d];
						if (nx == n + 1) nx = 1; if (ny == n + 1) ny = 1;
						if (nx == 0) nx = n; if (ny == 0) ny = n;
					}
					v[i][j].erase(v[i][j].begin());
					v[nx][ny].push_back({ { m, s },{ d,true } });
					if (v[i][j].empty()) break;
				}
			}
		}
		for (int i = 1; i <= n; i++) { // 이동여부 초기화
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k < v[i][j].size(); k++) v[i][j][k].second.second = false;
			}
		}
		for (int i = 1; i <= n; i++) { // 2개 이상의 파이어볼이 존재하는 경우 처리
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() < 2) continue;
				int sum_m, sum_s; sum_m = sum_s = 0;
				bool is_odd = true; bool all_same = true;
				if ((v[i][j][0].second.first) % 2 == 0) is_odd = false;
				for (int k = 0; k < v[i][j].size(); k++) {
					sum_m += v[i][j][k].first.first; sum_s += v[i][j][k].first.second;
					if (is_odd && (v[i][j][k].second.first) % 2 != 1) all_same = false;
					if (!is_odd && (v[i][j][k].second.first) % 2 != 0) all_same = false;
				}
				int new_m = sum_m / 5; int new_s = sum_s / v[i][j].size();
				int start_d = 1;
				if (all_same) start_d--;
				v[i][j].clear();
				if (new_m != 0) {
					for (int k = 0; k < 4; k++) {
						v[i][j].push_back({ { new_m, new_s },{ (k * 2) + start_d, false } });
					}
				}
			}
		}
	}
	int answer = 0;
	for (int i = 1; i <= n; i++) { 
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < v[i][j].size(); k++) {
				answer += v[i][j][k].first.first;
			}
		}
	}
	cout << answer;
	return 0;
}