[BOJ-Code] 20056 - 마법사 상어와 파이어볼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//입력: N, M, K, M개의 줄에 파이어볼정보.
//	출력 : K번 명령한 후 남아있는 파이어볼 질량의합.
//
//	1. 모든 파이어볼이 d 방향으로 s 만큼 이동
//	2. 이동이 끝난뒤 2개 이상의 파이어볼이 있는 칸에서 일이 발생함.
//	- 같은  칸에 있는 파이어볼은 모두 하나로 합쳐짐
//	- 파이어볼은 4개의 파이어볼로나누어짐
//	- 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같음
//	- 질량 = 합쳐진 파이어볼 / 5
//	- 속력 = 합쳐진 파이어볼 속력의 합 / 합쳐진 파이어볼의 개수
//	- 합쳐지는 파이어볼의 방향이 모두 홀수 or 짝수이면 방향은 0, 2, 4, 6 아니면 1, 3, 5, 7이됨.
//	- 질량이 0인 파이어볼은 소멸.

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
struct info {
	int m, s, d;
};
vector<info> FireBall_map[50][50];

int N, M, K;
int dy[] = { -1,-1,0,1,1,1,0,-1 };
int dx[] = { 0,1,1,1,0,-1,-1,-1 };

void init() {
	memset(FireBall_map, 0, sizeof(FireBall_map));
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		r--; c--;
		FireBall_map[r][c].push_back({ m,s,d });
	}
}
void FireBallGame() {
	vector<info> tmp_map[50][50];

	// 파이어볼 이동
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < FireBall_map[i][j].size(); k++) {
				int dir = FireBall_map[i][j][k].d;
				int speed = FireBall_map[i][j][k].s % N;
				int weight = FireBall_map[i][j][k].m;

				int ny = (i + dy[dir] * speed + N) % N;
				int nx = (j + dx[dir] * speed + N) % N;
				tmp_map[ny][nx].push_back({ weight,FireBall_map[i][j][k].s ,dir }); // 속도 원위치
			}
		}
	}

	// 2개 이상 겹친곳 정리하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			vector<info> newFireball;
			int fireballsize = tmp_map[i][j].size();
			if (fireballsize < 2) continue;
			int weight = 0, dir = 0, speed = 0;
			bool dirflag = false;
			int evencnt = 0, oddcnt = 0;
			for (int k = 0; k < fireballsize; k++) {
				weight += tmp_map[i][j][k].m;
				speed += tmp_map[i][j][k].s;
				if (tmp_map[i][j][k].d % 2 == 0) evencnt++;
				else oddcnt++;
			}
			if (oddcnt == 0 || evencnt == 0) {
				dirflag = true;
			}
			weight = weight / 5;
			speed = speed / fireballsize;
			if (weight == 0) {
				tmp_map[i][j].clear(); // 해당위치 비우기
				continue;
			}
			// 새로운 파이어볼 생성
			if (dirflag == true) { // 0 2 4 6
				for (int k = 0; k < 4; k++) {
					newFireball.push_back({ weight,speed,k * 2 });
				}
			}
			else {
				for (int k = 0; k < 4; k++) { // 1 3 5 7
					newFireball.push_back({ weight,speed,k * 2 + 1 });
				}
			}
			tmp_map[i][j] = newFireball;
		}
	}
	// 맵 갱신하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			FireBall_map[i][j] = tmp_map[i][j];
		}
	}
}

int findFireWeight() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < FireBall_map[i][j].size(); k++) {
				sum += FireBall_map[i][j][k].m;
			}
		}
	}
	return sum;
}
void printmap() {
	cout << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (FireBall_map[i][j].size() == 0)
				cout << 0 << " ";
			else cout << 1 << " ";
		}
		cout << endl;
	}
}

int main() {
	init();
	for (int i = 0; i < K; i++) {
		// 모든 파이어볼이 d 방향으로 s 만큼 이동
		FireBallGame();
		//printmap();
	}
	int result = findFireWeight();
	cout << result << endl;

}