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

문제

문제 바로가기> BOJ 20056번: 마법사 상어와 파이어볼

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

 

풀이

주의할점 

1. 파이어볼이 나눠진 후, 방향이 변화되어 제자리에 담긴다. 이동 x

2. 인덱스 `-`가 되지 않도록, N*s를 더해 준다. → 어짜피  modulo 하면 사라짐

 

#include<iostream>
#include<vector>
#define MAX 51
using namespace std;

struct FIREBALL { int m, s, d; };
vector<FIREBALL> map[MAX][MAX], moved_map[MAX][MAX];

int N, M, K;
int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void input() {
	cin >> N >> M >> K;

	int r, c, m, d, s;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> m >> s >> d;
		map[r - 1][c - 1].push_back({ m, s, d }); // 질량, 속력, 방향
	}
}

void move() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			for (int k = 0; k < map[r][c].size(); k++) {
				int m = map[r][c][k].m; // 질량
				int s = map[r][c][k].s; // 속력
				int d = map[r][c][k].d; // 방향

				// 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결
				int nr = (N*s + r + dr[d] * s) % N;
				int nc = (N*s + c + dc[d] * s) % N;
				moved_map[nr][nc].push_back({ m,s,d }); // move
			}
			map[r][c].clear(); // init for next
		}
	}
}

void divide() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (moved_map[r][c].size() < 2) map[r][c] = moved_map[r][c];
			else {
				// 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸
				int start = 0;
				int sum_m = 0, sum_s = 0;
				int first_d = (moved_map[r][c][0].d) % 2;
				for (int k = 0; k < moved_map[r][c].size(); k++) {
					sum_m += moved_map[r][c][k].m;
					sum_s += moved_map[r][c][k].s;
					if (first_d != (moved_map[r][c][k].d % 2)) start = 1;
				}
				int new_m = sum_m / 5; // 나누어진 파이어볼의 질량
				int new_s = sum_s / (int) moved_map[r][c].size(); // 나누어진 파이어볼의 속력
				if (new_m > 0) { // 질량이 0인 파이어볼은 소멸되어 없어짐
					for (int d = start; d < 8; d += 2) {
						map[r][c].push_back({ new_m, new_s, d });
					}
				}
			}
			moved_map[r][c].clear(); // init for next
		}
	}
}

void output() { // 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합
	int ans = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			for (int k = 0; k < map[r][c].size(); k++) ans += map[r][c][k].m;
		}
	} cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen("input.txt", "r", stdin); // task /f /PID [pid]
	input();
	while (K--) {
		move();
		divide();
	}
	output();
}