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

sol : 67' 20''

• 수행 시간 : 28ms
• 메모리 : 2812KB

Learnings

• 비트마스크를 연습해보자.

int mask = 0;
for (int k = 0; k < grid[i][j].size(); k++) {
	mask |= (1 << (grid[i][j][k].d % 2));
}

-> mask:1 ... 전부 짝수, mask:2 ... 전부 홀수, mask:3 ... 섞임

• 꼭 가지고 있어야 할 정보가 무엇인지 고민하는 습관을 실천해봤다.
• Fireball은 굳이 id를 구분해야 할 필요가 없다.
• 그러므로 임의의 객체정도로만 구분해주기로 판단.

#include <iostream>
#include <vector>

using namespace std;

#define EMPTY 0
#define MAX_N 51
#define DIAGONAL 1
#define ORTHOGONAL 0

// 1-base
const int ds[8][2] = {
	{-1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
	{1, 0},
	{1, -1},
	{0, -1},
	{-1, -1}
};

// m이 0이면 소멸 취급
struct Fireball {
	int m;
	int s;
	int d;

	Fireball() {}
	Fireball(int _m, int _s, int _d) :
		m(_m), s(_s), d(_d) { }
};

int n, m, k;
vector<Fireball> grid[MAX_N][MAX_N];
vector<Fireball> tempGrid[MAX_N][MAX_N];

void Init() {
	cin >> n >> m >> k;

	for (int i = 1; i <= m; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		grid[r][c].push_back(Fireball(m, s, d));
	}
}

void InitTempGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tempGrid[i][j].clear();
		}
	}
}

void DupGrid(vector<Fireball> from[MAX_N][MAX_N], vector<Fireball> to[MAX_N][MAX_N]) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

// 질량이 0인 파이어볼은 자동으로 삭제됨.
void Move() {
	InitTempGrid();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j].empty()) continue;

			for (int k = 0; k < grid[i][j].size(); k++) {
				if (grid[i][j][k].m == EMPTY) continue;

				int cm = grid[i][j][k].m, cs = grid[i][j][k].s, cd = grid[i][j][k].d;
				cs %= n;

				int ni = (i - 1 + ds[cd][0] * cs + n) % n + 1;
				int nj = (j - 1 + ds[cd][1] * cs + n) % n + 1;

				tempGrid[ni][nj].push_back(grid[i][j][k]);
			}
		}
	}

	DupGrid(tempGrid, grid);
}

void Merge() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j].size() >= 2) {
				int nextM = 0, nextS = 0, nextD = -1;
				int startD = grid[i][j][0].d % 2;
				
				for (int k = 0; k < grid[i][j].size(); k++) {
					nextM += grid[i][j][k].m;
					nextS += grid[i][j][k].s;
					if (nextD != -1) continue;
					if (grid[i][j][k].d % 2 != startD) nextD = DIAGONAL;
				}
				if (nextD == -1) nextD = ORTHOGONAL;
				nextM /= 5, nextS /= grid[i][j].size();

				// 질량이 0이 된 파이어볼은 자동 소멸됨.
				grid[i][j].clear();
				if (nextM == EMPTY)	continue;
				else {
					for (int k = 0; k < 4; k++) {
						grid[i][j].push_back(Fireball(nextM, nextS, nextD + k * 2));
					}
				}
			}
		}
	}
}

void PrintAnswer() {
	int totalM = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < grid[i][j].size(); k++) {
				totalM += grid[i][j][k].m;
			}
		}
	}
	cout << totalM;
}

int main() {
	Init();

	for (int turn = 1; turn <= k; turn++) {
		Move();

		Merge();
	}

	PrintAnswer();

	return 0;
}