ALGORITHM/BOJ
[백준] 20056 마법사 상어와 파이어볼
0298
2021. 4. 6. 22:30
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
2021-04-06
|
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
135
136
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main20056 {
static class Ball {
int r;
int c;
int m;
int s;
int d;
public Ball(int r, int c, int m, int s, int d) {
this.r = r;
this.c = c;
this.m = m;
this.s = s;
this.d = d;
}
}
public static LinkedList<Ball>[][] list;
public static Queue<Ball> q;
public static int N, M, K, answer;
public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
public static void move() {
int size = q.size();
while(size > 0) {
Ball b = q.poll();
assert b != null;
int r = b.r;
int c = b.c;
int m = b.m;
int s = b.s;
int d = b.d;
// 이동 좌표 계산 - 연결되어 있음
r += (dx[d] * (s % N));
c += (dy[d] * (s % N));
r = (r < 0) ? N+r : r;
c = (c < 0) ? N+c : c;
r = (r >= N) ? r-N : r;
c = (c >= N) ? c-N : c;
q.add(new Ball(r, c, m, s, d)); // q에 현재 파이어볼 정보 담기
size--;
}
}
public static void merge() {
answer = 0;
while(!q.isEmpty()) {
Ball b = q.poll();
int r = b.r;
int c = b.c;
int m = b.m;
int s = b.s;
int d = b.d;
list[r][c].add(new Ball(r, c, m, s, d)); // q에 있는 것들 list 좌표 값에 맞춰서 옮기기
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int size = list[i][j].size();
if(size > 1) { // 해당 좌표에 2개 이상의 파이어볼이 있다면
int mass = 0;
int speed = 0;
List<Integer> dir = new ArrayList<>();
for(int k = 0; k < list[i][j].size(); k++) {
Ball b = list[i][j].get(k);
mass += b.m; // 질량 합
speed += b.s; // 속도 합
dir.add(b.d); // dir 임시저장
}
mass /= 5;
speed /= size;
int base = dir.get(0) % 2; // dir 첫 번째 기준으로
int flag = 0; // 같으면 짝수
// dir
if(mass > 0) {
// 짝수 / 홀수가 다르면
for(int p = 1; p < dir.size(); p++) {
if(dir.get(p) % 2 != base) { // 하나라도 다르면 홀수
flag = 1;
break;
}
}
for(int p = flag; p < 8; p+=2) { // 짝/홀 시작
q.add(new Ball(i, j, mass, speed, p));
}
}
} else if(size == 1) { // 해당 좌표에 값이 하나밖에 없는 경우 그냥 queue에 넣어
q.add(new Ball(i, j, list[i][j].get(0).m, list[i][j].get(0).s, list[i][j].get(0).d));
}
}
}
Queue<Ball> temp = new LinkedList<>(q); // q 복사
while(!temp.isEmpty()) {
Ball b = temp.poll();
answer += b.m;
}
}
public static void init() {
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
list[i][j] = new LinkedList<>();
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new LinkedList[N][N];
q = new LinkedList<>();
answer = 0;
init();
for(int i = 0; i < M; i++) {
st = new StringTokenizer(bf.readLine());
int r = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken()) - 1;
int m = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
q.add(new Ball(r, c, m, s, d));
}
for(int i = 0; i < K; i++) {
move(); // 이동
merge(); // 합치고 나누고 ...
init(); // 좌표에 list 초기화
}
System.out.println(answer);
}
}
|
cs |
#문제풀이
주석으로 풀이를 썼다.
문제만 잘 읽어서 순서대로 구현하면 깔끔하고 어렵지 않게 구현할 수 있는 문제인데,,, 스스로 더럽게 만들었다,,, queue와 linkedlist 2개 따로 하지 않아도 되는데, 괜히 배열 두 번 안돌겠다고 하다가 이상한데서 헤매기만 했다;