Problem Solving
[백준/BOJ] 20056 마법사 상어와 파이어볼 (Java)
JYHAN
2020. 12. 19. 02:31
[백준/BOJ] 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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Fire {
int r,c,m,s,d;
int cnt;
int all; // 0:기타 1:홀 -1:짝
public Fire(int r, int c, int m, int s, int d, int cnt, int all) {
super();
this.r = r;
this.c = c;
this.m = m;
this.s = s;
this.d = d;
this.cnt = cnt;
this.all = all;
}
}
private static ArrayList<Fire> list;
private static int N, M, K;
private static int[] dx = {-1,-1,0,1,1,1,0,-1};
private static int[] dy = {0,1,1,1,0,-1,-1,-1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new ArrayList<Fire>();
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
Fire fire = null;
if(d%2==0) fire = new Fire(r,c,m,s,d,1,-1);
else if(d%2==1) fire = new Fire(r,c,m,s,d,1,1);
list.add(fire);
}
int ans = 0;
while(true) {
Fire[][] map = new Fire[N+1][N+1];
// 1.이동
move(map);
// 2.같은 칸 합치기 & 조건에 따라 4개로 파이어볼로 나누기
Merge(map);
if(--K == 0) break;
}
for(int i=0; i<list.size(); i++)
ans += list.get(i).m;
System.out.println(ans);
}
private static void move(Fire[][] map) {
int size = list.size();
while(size-->0) {
Fire temp = list.get(0); list.remove(0);
// r,c,m,s,d,cnt,all(짝홀/기타)
int r = temp.r;
int c = temp.c;
int d = temp.d;
int s = temp.s;
// 다음 좌표만 구하면 된다
// 1~N
int speed = s%N;
r = r + dx[d] * speed;
c = c + dy[d] * speed;
if(r > N) r -= N;
if(c > N) c -= N;
if(r < 1) r += N;
if(c < 1) c += N;
temp.r = r; temp.c = c;
if(map[r][c]==null) map[r][c] = temp;
else {
map[r][c].m += temp.m;
map[r][c].s += temp.s;
map[r][c].cnt++;
if(d%2==0 && map[r][c].all != -1) { // 짝 && 먼저 위치한 파이어볼이 짝 X
map[r][c].all = 0;
}else if(d%2==1 && map[r][c].all != 1) { // 홀 && 먼저 위치한 파이어볼이 홀 X
map[r][c].all = 0;
}
}
}
}
private static void Merge(Fire[][] map) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(map[i][j] !=null) {
if(map[i][j].cnt==1) { // 한 개
list.add(map[i][j]);
}else if(map[i][j].cnt>1) { // 여러개
int m = map[i][j].m/5; // 질량=질량의합/5
if(m==0) continue; // 질량 0 소멸
int s = map[i][j].s/map[i][j].cnt; // 속도=속도의합/개수
if(map[i][j].all==0) {// !(모두 짝||모두 홀)
for(int k=0; k<4; k++)
list.add(new Fire(i, j, m, s, k*2+1, 1, 1));
}else {
for(int k=0; k<4; k++)
list.add(new Fire(i, j, m, s, k*2, 1, -1));
}
}
}
}
}
}
}
|
cs |