[BOJ] 20056: 마법사 상어와 파이어볼 (C++)

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

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

걸린 시간 : 1시간 46분 45초

---

너무너무... 오래 걸려서 자신감을 떨어트린 문제....

파이어볼을 저장하는 자료구조를 처음에 multimap으로 접근했다가 말도 안되는 생각이란 걸 알았다.

그 후, 3차원 배열과 벡터를 번갈아가며 쓰는 것으로 결정했고, 다들 그렇게 많이 한 것 같다.

두 번째는, 좌표가 0~(N-1)이 아니라 1~N 이기 때문에, 좌표를 단순히 (% N) 과 같은 연산으로 하면 안된다.

이 두 개를 생각하느라 힘들었다...

자료구조

우선 파이어볼을 나타내는 구조체 fireball은 주어진 5개의 변수를 그대로 가지고 있는다.

그리고 "이동"을 하면 파이어볼의 배열 balls 에서 지도 형태의 board 로 옮겨가게 한다. (board는 2차원 배열의 각 위치에 fireball 벡터가 있는 3차원 벡터 형태이다.)

그 후 "합치기"를 하면 board 에서 balls 로 옮겨가게 한다.

즉 한 번의 실행이 끝나면 결과는 balls에 있다.

각 "이동"과 "합치기" 전에는 결과를 저장할 구조체를 모두 초기화시켜야 한다.

알고리즘

알고리즘은 전체적으로 "이동"을 나타내는 move() 함수와 "합치기"를 나타내는 join() 함수로 나뉜다.

• move()
  1. 결과를 저장할 board를 초기화한다.
  2. balls에 있는 모든 파이어볼을 이동시킨다. 이 때, 속력이 N일 때 다시 제자리로 오기 때문에 그냥 % N 연산을 한 결과로 이동시켜도 된다.
  3. 만약, 범위를 벗어났다면 조정해준다. 2번에서 이동의 크기를 N 이하로 조정했기 때문에 깊게 생각할 필요 없이 N을 더하거나 빼주면 된다.
  4. 파이어볼의 위치를 재조정하고 board 배열에 넣어준다.
• join()
  1. 결과를 저장할 balls를 초기화한다.
  2. board 배열을 모두 탐색한다.
     1. 해당 위치에 아무 파이어볼이 없으면 continue한다.
     2. 해당 위치에 파이어볼이 하나 있으면 그 파이어볼을 그대로 balls 벡터에 넣고 continue한다.
     3. 해당 위치에 파이어볼이 두 개 이상 있으면 실제 파이어볼을 합쳐야 한다. 이 때, 방향, 질량, 속력을 구해야 한다. 다음 1,2,3번을 실행한 후 나온 새로운 4개의 파이어볼을 balls에 넣는다.
        
        1. 방향은 벡터의 첫 방향을 2로 나눈 나머지를 tmp 라는 임시값으로 잡아둔다. 만약, 모든 파이어볼의 방향을 2로 나눴을 때 tmp와 같다면 방향은 0,2,4,6이 되므로 방향의 시작값인 dir에 0을 넣어준다. 아니라면 dir를 1로 변경한다.
        2. 질량은 모두 더한 후 5로 나눈다. 이 때, 질량이 0이라면 바로 continue 한다.
        3. 속력은 모두 더한 후 벡터의 크기로 나눈다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

struct fireball {
	int r, c, m, s, d;
};

int N, M, K;

vector<fireball> balls;
vector<fireball> board[51][51];
int dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void move() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			board[i][j].clear();
		}
	}
	for (fireball& ball : balls) {
		int nr = ball.r + dr[ball.d] * (ball.s % N);
		int nc = ball.c + dc[ball.d] * (ball.s % N);
		if (nr <= 0) nr = nr + N;
		if (nr > N) nr = nr - N;
		if (nc <= 0) nc = nc + N;
		if (nc > N) nc = nc - N;
		ball.r = nr;
		ball.c = nc;
		board[nr][nc].push_back(ball);
	}
}

void join() {
	balls.clear();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (board[i][j].size() == 0)
				continue;
			if (board[i][j].size() == 1) {
				balls.push_back(board[i][j][0]);
				continue;
			}
			int dir = 0, m = 0, s = 0;
			int tmp = board[i][j][0].d % 2;
			for (int k = 0; k < board[i][j].size(); k++) {
				if (board[i][j][k].d % 2 != tmp)
					dir = 1;
				m += board[i][j][k].m;
				s += board[i][j][k].s;
			}
			m /= 5;
			s /= board[i][j].size();
			if (m == 0) continue;
			for (int d = dir; d < 8; d += 2) {
				fireball ball = {i, j, m, s, d};
				balls.push_back(ball);
			}
		}
	}
}

int main(void) {
	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;
		fireball ball = {r, c, m, s, d};
		balls.push_back(ball);
	}
	while (K--) {
		move();
		join();
	}
	int ans = 0;
	for (fireball ball : balls) {
		ans += ball.m;
	}
	cout << ans;
	return 0;
}