[BOJ][삼성기출] 20056. 마법사 상어와 파이어볼

문제 접근

시뮬레이션 문제이다.

문제 흐름은 다음과 같다.

1. 모든 파이어볼을 방향으로 속력만큼 이동
2. 이동이 끝난 후, 같은 칸에 2개 이상의 파이어볼이 있다면
   모든 파이어볼을 하나로 합치고, 4개로 나눈다.
3. 나눈 파이어볼의 질량이 0이라면 파이어볼은 사라지고, 그렇지 않으면 새로 구한 질량과 속력을 가지는 4개의 파이어볼이 된다.

관건은 범위 제한이 없는 격자를 구현하는 것!
다음 위치가 격자 범위가 아니라면 scale함수를 통해 새로운 좌표를 설정해 주었다.
처음에 구성된 함수는 아래와 같은데, 주어진 4개 테케는 맞았는데 제출하니 0%에서 틀렸습니다. 가 나왔다.

if (nx > 0) {
	return nx % N;
}
else if (nx == 0) {
	return N;
}
else {
	return N - (abs(nx) % N);
}

이유는 nx이 N과 동일할 때 nx & N 연산의 결과가 0이 나오는 경우의 수를 포함하지 못했기 때문이었다.
이 부분만 수정하니 통과가 되었는데, 질문검색을 통해 알아냈다.


파이어볼을 나타내는 구조체인 fireball을 정의하고 fireball type의 vector를 정의하여 문제를 풀었다.
입력 받는 파이어볼들을 순서대로 vector에 넣으며 그 index를 각 파이어볼의 번호로 사용하였는데, 이 번호는 나중에 겹치는 파이어볼이 있는지를 판단할 때 이용하였다.

1. FB vector를 traverse하며 아직 사라지지 않은(is_live가 true인) 파이어볼을 움직인다.
   이때 움직인 위치에 파이어볼의 번호를 저장한다.
2. 2개 이상의 파이어볼이 한 공간에 있을 경우, 저장된 파이어볼의 번호를 통해 해당 파이어볼의 정보를 불러와 필요한 연산을 한다. (새로운 질량, 속력 구하기)
   겹치는 파이어볼은 어떤 경우든 다음 스텝에 존재하지 않아야 하기 때문에 (사라지든, 새로운 파이어볼로 나뉘든) is_live에 false를 assign 해준다.
3. 새로 구한 질량이 0일 경우 새로운 파이어볼을 만들지 않는다.
4. 0이 아닐 경우, 새로운 파이어볼을 만들어 FB vector에 넣어준다.

+) 파이어볼을 나눌 때 합쳐진 칸에서 4개로 쪼갠 뒤 서로 다른 4개의 방향을 주는 건데, 이 부분이 문제에 명쾌하게 주어지지 않아서 조금 헷갈렸다.

풀이

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef struct fireball {
	int num;
	int x;
	int y;
	int m;
	int s;
	int d;
	bool is_live;
} fireball;

int N, M, K, rst;
vector<fireball> FB;
vector<int> map[51][51];
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

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 tmp = {i, r, c, m, s, d, true};
		FB.push_back(tmp);
	}
}

int is_range(int x) {
	if (x >= 1 && x <= N) return true;
	return false;
}

int scale(int nx) {
	if (nx > N)   nx = nx % N;
	if (nx < 1)   nx = N - abs(nx) % N;
	return nx;
}

void move() {
	for (int i = 0; i < FB.size(); i++) {
		if (!FB[i].is_live) continue;
		int nx = FB[i].x + FB[i].s * dx[FB[i].d];
		int ny = FB[i].y + FB[i].s * dy[FB[i].d];
		if (!is_range(nx)) nx = scale(nx);
		if (!is_range(ny)) ny = scale(ny);

		FB[i].x = nx;
		FB[i].y = ny;
		map[nx][ny].push_back(FB[i].num);
	}
}

void adjust() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j].size() < 2) continue;

			int msum = 0, ssum = 0;
			bool is_even = true, is_odd = true;
			for (int idx = 0; idx < map[i][j].size(); idx++) {
				int num = map[i][j][idx];
				msum += FB[num].m;
				ssum += FB[num].s;
				if (FB[num].d % 2 == 0) is_odd = false;
				else is_even = false;
				FB[num].is_live = false;			
			}

			int nm = msum / 5;
			int ns = ssum / map[i][j].size();
			if (nm == 0) continue;
			if (is_even || is_odd) { // 0, 2, 4, 6
				int nd = 0;
				for (int iter = 0; iter < 4; iter++) {
					fireball tmp = { FB.size(), i, j, nm, ns, nd, true };
					FB.push_back(tmp);
					nd += 2;
				}
			}
			else { // 1, 3, 5, 7
				int nd = 1;
				for (int iter = 0; iter < 4; iter++) {
					fireball tmp = { FB.size(), i, j, nm, ns, nd, true };
					FB.push_back(tmp);
					nd += 2;
				}
			}
		}
	}
}

void reset() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			while (!map[i][j].empty()) {
				map[i][j].pop_back();
			}
		}
	}
}

void cal_rst() {
	rst = 0;
	for (int idx = 0; idx < FB.size(); idx++) {
		if (!FB[idx].is_live) continue;
		rst += FB[idx].m;
	}
}

void solve() {
	while (K-- > 0) {
		reset(); // make map vector empty
		move();
		adjust();
	}
	cal_rst();
}

int main() {
	input();
	solve();
	cout << rst << endl;
}