[BOJ/C++] 16236번 아기 상어
문제
문제 해석
아기 상어의 크기가 처음엔 2로 고정되어 있고, 크기와 같은 수의 물고기를 먹었을 때 크기가 1 증가한다.
- 아기 상어가 먹은 물고기의 수와 현재 크기를 기록해야 한다.
먹을 수 있는 물고기는 아기 상어의 크기보다 작은 물고기이다. 아기 상어의 크기와 같은 물고기는 지나갈 수 있다.
- 아기 상어보다 크기가 큰 물고기는 지나갈 수 없으므로, 삥 둘러 간다는 점에서 거리를 기록해야 한다.
- ✅ 처음에는 단순히
(3, 4)위치의 아기 상어가(1, 2)위치의 물고기를 먹으러 갈 때 이동 거리가abs(3 - 1) + abs(4 - 2)라고 생각했는데, 사이에 아기 상어보다 크기가 큰 물고기가 있다면 지나갈 수 없으므로 잘못된 구현이다. - 단순히 크기만 작으면 먹을 수 있는 것이 아니다. 아기 상어가 이동 가능해야 하므로, 크기마다 물고기의 위치를 기록하는 방법으로는 풀 수 없다. BFS를 이용해 아기 상어의 이동 가능성을 판단해야 한다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 크기가 작은 물고기의 위치에 이동이 가능하다면, 물고기와 아기 상어 사이의 거리를 기록한다.
- ✅ 거리가 같을 때 비교 기준이 문제에 주어졌으므로, cmp 함수를 구현해야 한다.
놓친 부분
✅ 아기 상어가 물고기를 먹으러 가는 이동 거리를 단순히 행과 열 차이로만 계산한 것.
✅ 거리가 가까운 것이 문제에서 주어진 제1 비교 원칙인데, 이를 포함시키지 않은 것
구현 방향
변수 선언
아기 상어의 위치로부터 먹을 수 있는 물고기를 탐색할 때 BFS 알고리즘을 사용하는데, 이때 방문한 위치를 기록해야 q를 무한히 도는 현상에 빠지지 않는다.
아기 상어가 이동하면서 만난 먹을 수 있는 물고기들은 v에 기록한다. 필요한 정보들이 3개 이상일 때는 구조체를 만들어서 관리한다.
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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int board[21][21];
int visited[21][21];
typedef struct shark {
int row, col, size, fish, dist;
};
typedef struct fish {
int row, col, dist;
};
queue<shark> q;
vector<fish> v;
int shark_row;
int shark_col;
int shark_size;
int shark_fish;
int answer = 0;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int main()
// input
✅ 아기 상어 위치를 표시하는 9를 0으로 바꾸지 않으면 9도 물고기 크기로 인식한다. 돌아서 물고기를 먹으러 가는 오류가 생기고, 결국 답이 틀리니 주의해야 한다.
// initialize
여러 번 사용하는 visited, v는 while 문 안에서 초기화 해야 한다.
// find food bfs
아기 상어의 위치에서 먹을 수 있는 물고기를 찾는다. BFS 알고리즘을 이용한다.
// sort
bfs를 하고 나면 v에 먹을 수 있는 물고기의 정보가 담겨 있다. 우선순위에 따라 정렬하고 먹으러 이동한다.
// stop condition
만약 먹을 수 있는 물고기가 없다면, 종료하고 정답을 출력한다.
// eat and update shark
물고기의 위치로 아기 상어를 이동시키고, 먹은 물고기의 개수를 증가시킨다. 만약 먹은 물고기의 개수가 현재 크기와 같다면, 크기를 +1 하고 먹은 물고기의 개수를 초기화 한다.
✅ 아기 상어가 물고기를 먹은 자리는 비어 있게 되므로, 0으로 바꿔야 한다.
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
int main() {
// input
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
if (board[i][j] == 9) {
shark_row = i;
shark_col = j;
board[i][j] = 0; // warning
}
}
}
shark_size = 2;
shark_fish = 0;
while (true) {
// initialize
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visited[i][j] = 0;
}
}
v.clear();
// find food bfs
q.push({ shark_row, shark_col, shark_size, shark_fish, 0 });
visited[shark_row][shark_col] = 1;
bfs();
// sort food v
sort(v.begin(), v.end(), cmp);
// stop condition : nothing to eat fish
if (v.size() == 0) {
break;
}
// eat and update shark
answer += v[0].dist;
shark_row = v[0].row;
shark_col = v[0].col;
if (shark_size == shark_fish + 1) {
shark_size += 1;
shark_fish = 0;
}
else {
shark_fish++;
}
board[shark_row][shark_col] = 0;
}
cout << answer;
}
void bfs()
아기 상어가 먹을 수 있는 물고기를 찾는다. 크기가 같거나 작은 물고기만 지나갈 수 있으므로, dist 정보를 기록하는 것이 중요하다.
범위를 체크하는 것도 신경써야 한다! 범위에 있는지, 이동 가능한지, 방문하지 않았는지 총 세 가지를 확인해야 한다.
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
void bfs() {
while (!q.empty()) {
int row = q.front().row;
int col = q.front().col;
int size = q.front().size;
int fish = q.front().fish;
int dist = q.front().dist;
q.pop();
// can eat?
for (int d = 0; d < 4; d++) {
int next_row = row + dx[d];
int next_col = col + dy[d];
if (next_row >= 0 && next_row < N
&& next_col >= 0 && next_col < N
&& board[next_row][next_col] <= size
&& visited[next_row][next_col] != 1) {
q.push({ next_row, next_col, size, fish, dist + 1 });
if (board[next_row][next_col] > 0
&& board[next_row][next_col] < size) {
v.push_back({ next_row, next_col, dist + 1});
}
visited[next_row][next_col] = 1;
}
}
}
}
bool cmp(fish a, fish b)
✅ 문제에 주어진 우선 순위에 따라 정확히 구현해야 한다. 특히 C++는 두 값이 같은 경우에 false를 반환해야 함에 주의한다.
1
2
3
4
5
6
7
8
9
10
11
12
bool cmp(fish a, fish b) {
if (a.dist < b.dist) return true;
else if (a.dist == b.dist) {
if (a.row < b.row) return true;
else if (a.row == b.row) {
if (a.col < b.col) return true;
else return false;
}
else return false;
}
else return false;
}