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

1. 문제 링크

문제 링크

2. 풀이

특정 알고리즘 지식은 요구하지 않고, 단순 구현력으로 승부보는 문제입니다.
하나씩 차근차근 구현해봅시다.

1. 파이어볼과 격자 정의

queue<tuple<int, int, int, int>> board[SIZE][SIZE];

파이어볼은 tuple로 정의했고 순서대로

• 질량
• 속도
• 방향
• 움직였는지 여부

의 정보를 가지게 했습니다.
파이어볼들은 서로 같은 좌표에 있을 수 있기 때문에
격자를 이차원 큐배열로 선언했습니다.

2. 파이어볼 이동

int adjustCoord(int a) {
	return a >= n
		? a - n
		: a < 0
		? a + n
		: a;
}

// 1. 파이어볼 이동
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		int size = board[i][j].size();

		// 큐의 원소들을 하나씩 순회하며 움직이지 않은 파이어볼을 이동시킴
		while (size--) {
			int m, s, d, isMove;

			tie(m, s, d, isMove) = board[i][j].front();

			// 이동한 애라면 넘어가기
			if (isMove) {
				board[i][j].push(board[i][j].front());
				board[i][j].pop();
				continue;
			}

			board[i][j].pop();

			// 이동시키기
			int y = adjustCoord(i + my[d] * (s % n));
			int x = adjustCoord(j + mx[d] * (s % n));

			board[y][x].push({ m, s, d, 1 });
		}
	}
}

파이어볼을 이동시킬 때는 단순히 격자를 전체 순회하면서
현재 턴에 움직이지 않은 파이어볼들만 이동시킵니다.
이 때 이동시킨 파이어볼이 다른 좌표에서 또 이동할 수 있기 때문에
isMove라는 상태값으로 판단해서 움직이지 않은 파이어볼들만 움직여줍니다.

3. 파이어볼 합치기

// 2. 파이어볼 합치기
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		int size = board[i][j].size();

		// 사이즈 1이하면 움직임 초기화하고 넘어감
		if (size <= 1) {
			if (size == 1) {
				int m, s, d, isMove;

				tie(m, s, d, isMove) = board[i][j].front();
				board[i][j].pop();
				board[i][j].push({ m, s, d, 0 });
			}

			continue;
		}

		// 질량, 속도 합산
		int sumM = 0, sumS = 0;

		// 홀짝
		int oddEven[2] = { 0, 0 };

		while (!board[i][j].empty()) {
			int m, s, d, isMove;

			tie(m, s, d, isMove) = board[i][j].front();
			board[i][j].pop();

			sumM += m;
			sumS += s;
			oddEven[d % 2] = 1;
		}

		sumM = sumM / 5;

		// 질량이 0이면 소멸
		if (sumM <= 0) continue;

		sumS = sumS / size;

		int startD = oddEven[0] == 1 && oddEven[1] == 1 ? 1 : 0;

		for (int k = 0; k < 4; k++) {
			board[i][j].push({ sumM, sumS, startD, 0 });
			startD += 2;
		}
	}
}

또 한 번 전체 격자를 순회하면서 파이어볼 혼자 있을 땐 isMove를 0으로 초기화하고
두 개 이상일 땐 합친 다음에 4개로 나누어줍니다.

이와 같은 로직을 총 k번 반복한 뒤, 격자에 남은 파이어볼의 질량의 총합을 구하면 됩니다.

3. 전체 코드

#define SIZE 50
#include <bits/stdc++.h>

using namespace std;

int n, m, k;
int my[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int mx[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
queue<tuple<int, int, int, int>> board[SIZE][SIZE];

int adjustCoord(int a) {
	return a >= n
		? a - n
		: a < 0
		? a + n
		: a;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	while (m--) {
		int r, c, m, s, d;

		cin >> r >> c >> m >> s >> d;

		board[r - 1][c - 1].push({ m, s, d, 0 });
	}

	while (k--) {
		// 1. 파이어볼 이동
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int size = board[i][j].size();

				// 큐의 원소들을 하나씩 순회하며 움직이지 않은 파이어볼을 이동시킴
				while (size--) {
					int m, s, d, isMove;

					tie(m, s, d, isMove) = board[i][j].front();

					// 이동한 애라면 넘어가기
					if (isMove) {
						board[i][j].push(board[i][j].front());
						board[i][j].pop();
						continue;
					}

					board[i][j].pop();

					// 이동시키기
					int y = adjustCoord(i + my[d] * (s % n));
					int x = adjustCoord(j + mx[d] * (s % n));

					board[y][x].push({ m, s, d, 1 });
				}
			}
		}

		// 2. 파이어볼 합치기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int size = board[i][j].size();

				// 사이즈 1이하면 움직임 초기화하고 넘어감
				if (size <= 1) {
					if (size == 1) {
						int m, s, d, isMove;

						tie(m, s, d, isMove) = board[i][j].front();
						board[i][j].pop();
						board[i][j].push({ m, s, d, 0 });
					}

					continue;
				}

				// 질량, 속도 합산
				int sumM = 0, sumS = 0;

				// 홀짝
				int oddEven[2] = { 0, 0 };

				while (!board[i][j].empty()) {
					int m, s, d, isMove;

					tie(m, s, d, isMove) = board[i][j].front();
					board[i][j].pop();

					sumM += m;
					sumS += s;
					oddEven[d % 2] = 1;
				}

				sumM = sumM / 5;

				// 질량이 0이면 소멸
				if (sumM <= 0) continue;

				sumS = sumS / size;

				int startD = oddEven[0] == 1 && oddEven[1] == 1 ? 1 : 0;

				for (int k = 0; k < 4; k++) {
					board[i][j].push({ sumM, sumS, startD, 0 });
					startD += 2;
				}
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			while (!board[i][j].empty()) {
				int m, s, d, isMove;

				tie(m, s, d, isMove) = board[i][j].front();
				board[i][j].pop();

				ans += m;
			}
		}
	}

	cout << ans;

	return 0;
}