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

---

[BOJ 20056(G5)리뷰]

삼성SW 역량테스트 기출문제다.

문제에 주어진 조건에 따라 천천히 시뮬레이션 하듯이 구현하면 된다. 효율적으로 풀어보려고 노력해보다 생각보다 시간이 많이 걸렸다.

문제에서 주의해야 할 부분은 N*N맵이 서로 이어져있다는것이다. 1번행에서 1칸 위로 올라가게되면 N번행이 나오고 N번열에서 1번 오른쪽으로 이동하게되면 1번 열이 나오는 식이다. 따라서 이 부분에 대한 변환식을 따로 구현했다.

int getRotation(int cur) {
	if (cur < 0) {
		int d = cur % N;
		if (d != 0) {
			d += N;
		}
		return d;
	}
	else if (cur >= N) {
		return cur % N;
	}
	else {
		return cur;
	}
}

내가봐도 효율적으로 보이진 않으나 기발한 방법이 떠오르지 않아 그냥 이렇게 구현했다. 이동하고자 하는 좌표를 넣으면 맵의 크기에맞게 알맞은 위치를 반환 해 준다.

그리고 info라는 구조체를 구현하여 파이어볼의 좌표, 질량, 속도, 방향 등을 저장하도록 했고, N*N맵을 벡터로 구현하여 파이어볼을 여러개 담을 수 있도록 했다.

그리고 실질적으로 이동이 이루어지는 것은 fList라는 파이어볼의 위치와 정보를 담은 벡터를 통해 구현했다. N*N맵을 돌며 파이어볼이 있는 위치에 대해 이동하도록 구현하면 되겠지만, 그냥 조금 더 효율적으로 해보겠다고 이렇게 했는데 여기서 실수를 많이했다..

과정은 크게 '1.파이어볼의 이동, 2.두개이상 파이어볼의 합체 및 분해' 로 이루어진다. 

파이어볼을 저장하고, 이동하는 부분만 주의하면 나머지는 문제에 주어진 조건대로만 하면 되기에 크게 어렵진 않다. 항상 파이어볼을 처리할때는 같은 턴에 작업이 이루어지는 파이어볼이 다른 파이어볼에게 영향을 끼치면 안된다는 점이다. 이 점을 주의하여 구현하자.

/*
	21.01.27
	BOJ : 20056 마법사 상어와 파이어볼 (https://www.acmicpc.net/problem/20056)
	시뮬레이션
*/
#include <bits/stdc++.h>
using namespace std;

struct info {
	int r;
	int c;
	int m;
	int s;
	int d;
};

int N, M, K;
vector <info> board[51][51];
vector <info> fList;

int total = 0;

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

int dir1[4] = { 0,2,4,6 };
int dir2[4] = { 1,3,5,7 };

int getRotation(int cur) {
	if (cur < 0) {
		int d = cur % N;
		if (d != 0) {
			d += N;
		}
		return d;
	}
	else if (cur >= N) {
		return cur % N;
	}
	else {
		return cur;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    
	cin >> N >> M >> K;

	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		board[r - 1][c - 1].push_back({ m,s,d });
		fList.push_back({ r - 1,c - 1,m,s,d });
		total += m;
	}
	
	while (K--) {
		int len = fList.size();
	
		//이동 처리
		vector <info> temp;
		for (int i = 0; i < len; i++) {
			auto cur = fList[i];
	
			int nr = cur.r + dx[cur.d] * cur.s;
			int nc = cur.c + dy[cur.d] * cur.s;
	
			nr = getRotation(nr);
			nc = getRotation(nc);
		
			temp.push_back({ nr,nc,cur.m,cur.s,cur.d });
			board[cur.r][cur.c].clear();
		}

		for (auto cur : temp) {
			board[cur.r][cur.c].push_back({ cur.r,cur.c,cur.m,cur.s,cur.d });
		}

		fList.clear();
		//파이어볼 합치고 나누기.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j].empty()) continue;
				else {
					if (board[i][j].size() == 1) {
						auto cur = board[i][j].front();
						fList.push_back({ i,j,cur.m,cur.s,cur.d });
						board[i][j].clear();
						continue;
					}
				}

				int sum_m = 0;
				int sum_s = 0;
				bool odd = true;
				bool even = true;
				vector <int> idx;
				for (auto cur : board[i][j]) {
					sum_m += cur.m;
					sum_s += cur.s;
					if (cur.d % 2 == 0) {
						odd = false;
					}
					else {
						even = false;
					}
				}

				int newm = sum_m / 5;
				int news = sum_s / (int)board[i][j].size();

				total -= sum_m;
				total += (newm * 4);

				int* newd;
				if (even || odd) { //모두 홀수거나 짝수
					newd = dir1;
				}
				else {
					newd = dir2;
				}

				if (newm == 0) { //질량이 0일경우 소멸
					board[i][j].clear();
					continue;
				}

				for (int dir = 0; dir < 4; dir++) {
					fList.push_back({ i,j,newm,news,newd[dir] });
				}

				board[i][j].clear();
			}
		}
	}

	cout << total;

	return 0;
}