● 종료 로그를 postHandle이 아니라 afterCompletion에서 실행하는 이유
-> 예외 발생하면 postHandle이 호출되지 않기 때문
● 요청 로그 구분하기 위해 uuid 생성
서블릿 필터는 지역 변수로 해결 가능하지만, 스프링 인터셉터는 호출 시점이 분리되어 있음. preHandle에서 생성한 값을 postHandle, afterCompletion에서 사용하려면 request에 담아두어야 함. (싱글톤처럼 사용되기 때문에 멤버 변수에 담아두면 위험함)
-> 큐에 상어의 다음 위치 삽입: q.push({ nr, nc, ... }) ------------------- ★
-> 현재 위치에서 제거: arr[row][col] = {0, 0, 0, 0, 0}
③ 큐에 있는 상어를 하나씩 꺼내서 상어의 새 위치를 배열에 반영
-> (현재 상어 크기) > (기존에 있는 상어 크기) ? 현재 상어 : 기존 상어
}
★ 큐에 상어의 다음 위치를 삽입하는 이유
상어의 다음 위치 계산 한 뒤에 (nr, nc) 상어를 바로 이동시키면 기존 (nr, nc) 위치에 있던 상어의 정보가 덮어씌워져서 계산을 할 수 없다. 이를 방지하기 위해 상어의 새 위치를 계산 즉시 반영시키지 않고 Queue에 저장해놨다가, 모든 상어의 새 위치가 계산된 후에 상어의 새 위치를 반영한다.
ex)
A 상어가 (4, 2) -> (4, 3)으로 이동하고, B 상어가 (4, 3)에 위치할 경우
A 상어를 (4, 3)으로 이동시키면 B 상어의 새 위치를 계산하지 못함
상어의 다음 위치 계산
C = 5
속도가 0일 때와 8일 때 방향, 위치 모두 동일한 것을 알 수 있다.
(현재 위치) mod 8 일 때 동일 -> (현재 위치) mod (5 - 1) * 2 = (현재 위치) mod (c - 1) * 2
이렇게 하면 방향 전환 하는 경우를 두 번만 고려하면 된다.
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
137
138
#include<iostream>
#include<algorithm>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
usingnamespacestd;
struct Node {
int r;
int c;
int speed;
int direction;
intsize;
};
int r, c, m, ans;
Node arr[101][101];
bool isSharkExist(int i, int j);
void removeShark(int i, int j);
void input();
void catchShark(int i, int j) {
ans += arr[i][j].size;
removeShark(i, j);
}
queue<Node> q;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
// 1. 낚시왕이 오른쪽으로 한 칸 이동한다.
rep(pos, c) {
// 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.상어를 잡으면 격자판에서 잡은 상어가 사라진다.
rep(row, r) {
if (isSharkExist(row, pos)) {
catchShark(row, pos);
break;
}
}
// 3. 상어가 이동한다.
rep(row, r) {
rep(col, c) {
if (isSharkExist(row, col)) {
Node& now = arr[row][col];
int nr = row;
int nc = col;
int move = now.speed;
// 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
// 1: 상, 2: 하, 3: 우, 4: 좌
if (now.direction ==1) {
move %= (r -1) *2;
nr = row - move;
if (nr <0) {
now.direction =2;
nr *=-1;
if (nr >= r) {
now.direction =1;
nr = (r -1) *2- nr;
}
}
}
elseif (now.direction ==2) {
move %= (r -1) *2;
nr = row + move;
if (nr >= r) {
now.direction =1;
nr = (r -1) *2- nr;
if (nr <0) {
now.direction =2;
nr *=-1;
}
}
}
elseif (now.direction ==3) {
move %= (c -1) *2;
nc = col + move;
if (nc >= c) {
now.direction =4;
nc = (c -1) *2- nc;
if (nc <0) {
now.direction =3;
nc *=-1;
}
}
}
elseif (now.direction ==4) {
move %= (c -1) *2;
nc = col - move;
if (nc <0) {
now.direction =3;
nc *=-1;
if (nc >= c) {
now.direction =4;
nc = (c -1) *2- nc;
}
}
}
// 상어가 이동할 좌표를 구하고 난 뒤, 즉시 새 위치로 이동시키면 (arr[nr][nc])
// 원래 [nr][nc]에 있는 상어를 덮어쓰게 됨. 따라서, 해당 상어는 이동하지 못함.
드디어 solved.ac 플레를 찍었다. 세그먼트 트리, lazy propagation 문제들은 난이도가 높아서 한 문제만 풀어도 경험치가 많이 올랐다. 알고리즘 자체가 어려워서 그렇지, 한 번 이해하니까 평소에는 힘들게 풀었던 골드1, 플레5 문제들도 풀 만했다. 하지만 응용 문제는 아직 공부를 많이 해야할 것 같다.
