16236 아기상어
16236 아기상어
최단거리 탐색 응용버전
다른사람들의 풀이를 볼때마다 어떻게 이런 생각을 하는지 대단하다는 생각이 든다
다양한 방법들을 많이 알아둬서, 언젠가 유용하게 쓸 수 있으면 좋겠다
1. 문제
간단 설명
N * N 크기의 공간에 아기상어가 움직이면서 물고기를 잡아먹는다 자신보다 작은 물고기만 먹을 수 있다 맵에 먹을 물고기가 더 이상 없으면, 종료하고 현재까지 걸린 시간을 출력한다
2. 문제 분석
필요변수
- 맵 크기
int N, 맵int map[26][26], 방문 체크 맵int map[26][26](bool도 가능) - 상어의 정보를 저장할 구조체
struct Shark. y, x좌표, 현재 크기, 먹은 물고기의 수를 저장한다 - 노드의 정보를 저장할 구조체
struct Node. y, x좌표, 현재까지 거리 정보, ‘<’ 연산자 오버로딩이 필요 - 우선순위 큐
priority_queue<Node> pq- 우선순위 큐를 이용하면 우선순위가 높은 원소가 먼저 나가도록 할 수 있다
- 이 우선순위를 Node 구조체에서 정의해줌
- 먹을 수 있는 거리가 가장 가까운 물고기가 우선순위가 높도록 배정한다
주의점
- 시간초과에 주의할 것!
- 먹을 수 있는 물고기가 1마리 보다 많다면, 가장 가까운 물고기를 먹으러 간다
- 최단거리 계산을 어떻게 할 것인지?
- 세부 조건들이 많은 문제이므로 구현에 주의할 것
알고리즘
1. 첫번째 시도
- 시간초과가 났음. 아마 반복문 내에서 먹이 큐에 저장된 각 원소들마다 BFS를 돌려서 오버된 듯
- 먹이 큐에 저장할 때 부터 거리순으로 정렬하면 BFS 탐색에 걸리는 시간을 줄일 수 있을듯 싶다
- Prioirt Queue를 이용. 우선순위 큐는 큐에 저장된 원소를 오름차순으로 혹은 내림차순으로 유지할 수 있다
1
2
3
4
5
6
7
8
9
10
1. 입력 및 상어 위치 저장
2. 먹이 큐가 빌때까지 다음을 반복한다
2-1. 2중 for문으로 먹이 스캔
2-2. 큐에 저장된 먹이들을 BFS를 돌려 최단거리를 찾는다
2-3. 최단거리 먹이를 타겟으로 설정한다
2-4. 상어가 먹이를 먹는다
2-4-1. 이동 거리만큼 시간 증가
2-4-2. 상어 위치 변경 및 맵 갱신
2-4-3. 상어 레벨업 판별
3. 2번이 종료되면 걸린시간을 출력한다
2. 두번째 시도 : 우선순위 큐 이용
- 물고기와의 위치를 BFS로 계산하는것이 아닌, 현재 상어의 위치를 넣고 레이더가 뻗어나가는 방식을 이용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. 입력 및 상어 위치 저장
2. 우선순위 큐를 이용한 BFS 최단경로 탐색
2-1. 큐의 맨 앞을 꺼내 먹을수 있는 사이즈인지 판별
2-1-1. 먹을수 있는 사이즈라면, 상어를 먹이 위치로 이동시킴
2-1-2. 상어가 사이즈가 커질만큼 충분히 먹었는지 확인 후 사이즈 변경
2-1-3. 맵에서 먹이 삭제 후 방문 배열 초기화
2-1-4. 우선순위 큐를 초기화
2-1-5. 시간초를 현재까지의 거리로 저장
2-2. 먹을 수 없는 사이즈거나 비어있는 칸이라면, 4방향 탐색 시작
2-2-1. 경계 밖이라면 패스
2-2-2. 더 큰 물고기를 만난다면 패스
2-2-3. 이미 방문한곳이라면 패스
2-2-4. 위 조건들을 통과했다면, 방문 표시 후, 우선순위 큐에 거리 +1 후 넣는다
3. 저장된 시간초를 출력한다
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
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
#include <iostream>
#include <queue>
#include <string.h>
#define MAX 21
using namespace std;
int N;
int map[MAX][MAX];
int visited[MAX][MAX];
struct Node {
int y;
int x;
int dis;
// 오름차순으로 정렬
bool operator<(const Node& b) const {
if (dis != b.dis) return dis > b.dis; // 1. 거리 우선 비교
if (y != b.y) return y > b.y; // 2. y 좌표 비교
else return x > b.x; // 3. x 좌표 비교
}
};
struct Shark {
int y;
int x;
int level;
int eaten;
// 레벨업 조건을 만족하면 사이즈가 증가한다
void CheckLevelUP() {
if (this->eaten == this->level) {
this->eaten = 0;
this->level++;
}
}
} shark;
int direct[4][2] = { -1,0,0,1,1,0,0,-1 }; // ↑ → ↓ ←
int main() {
// 1. 입력
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
cin >> map[y][x];
if (map[y][x] == 9) {
shark.y = y;
shark.x = x;
map[y][x] = 0; // 이동 경로 계산을위해 미리 0으로 바꾸기
shark.level = 2;
shark.eaten = 0;
}
}
}
// 2. 아기상어의 현재 위치부터 먹이 탐색
// 상어의 현재 위치로부터 뻗어나가면서 먹을수 있는 물고기가 레이더에 걸리는지 체크한다
queue<Node> pq;
int seconds = 0;
visited[shark.y][shark.x] = 1;
pq.push({ shark.y, shark.x, 0 });
while (!pq.empty()) {
Node now = pq.front();
pq.pop();
// 1. now 가 먹을수 있는 사이즈라면
if (map[now.y][now.x] != 0 && map[now.y][now.x] < shark.level) {
// 먹으로 맵 이동
shark.y = now.y;
shark.x = now.x;
shark.eaten++;
shark.CheckLevelUP();
// 맵 갱신 및 방문체크 배열 초기화
map[now.y][now.x] = 0;
memset(visited, 0, sizeof(visited));
// 큐 초기화
while (!pq.empty()) pq.pop();
seconds = now.dis;
}
for (int t = 0; t < 4; t++) {
int dy = now.y + direct[t][0];
int dx = now.x + direct[t][1];
if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
if (shark.level < map[dy][dx]) continue; // 더 큰 물고기는 통과 불가
if (visited[dy][dx] == 1) continue; //
visited[dy][dx] = 1;
pq.push({ dy, dx, now.dis + 1 });
}
}
cout << seconds;
return 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
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
139
140
141
// 첫번째 시도한 코드. 답은 원하는대로 출력되나 시간초과
/*
*/
#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 21
using namespace std;
int N;
int map[MAX][MAX];
queue<pair<int, int>> prey;
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 }; // →↓←↑순으로 시도
struct shark {
int y;
int x;
int level;
int eaten_fish;
} baby_shark;
struct node {
int y;
int x;
int level;
};
// 출발좌표와 도착좌표를 받아 최단거리를 BFS로 계산하는 함수
// 도달할 수 있으면 최단거리를, 없다면 -1을 리턴한다
int BFS(int start_y, int start_x, int end_y, int end_x) {
queue<node> qu;
int visited[MAX][MAX];
qu.push({ start_y, start_x, 0});
visited[start_y][start_x] = 1;
while (!qu.empty()) {
node now = qu.front();
qu.pop();
// 도착지라면
if (now.y == end_y && now.x == end_x) {
return now.level;
}
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue; // 경계처리
if (map[dy][dx] > baby_shark.level) continue; // 상어보다 큰 물고기는 못지나감
if(visited[dy][dx] == 1) continue;
visited[dy][dx] = 1;
qu.push({ dy, dx, now.level + 1 });
}
}
return -1;
}
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
cin >> map[y][x];
if (map[y][x] == 9) {
baby_shark.y = y;
baby_shark.x = x;
baby_shark.level = 2;
baby_shark.eaten_fish = 0;
}
}
}
int seconds = 0;
while (1) {
// 1. 먹이 스캔
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (map[y][x] != 0 && map[y][x] < baby_shark.level) {
prey.push(make_pair(y, x));
}
}
}
// 2. 먹이 큐가 비어있다면 종료
if (prey.empty())
break;
// 3. 먹이들 중 최단 거리 확인
pair<int, int> target;
int min_dis = 21e8;
while (!prey.empty()) {
pair<int, int> now = prey.front();
prey.pop();
// 상어와 먹이의 거리 계산
int new_dis = BFS(baby_shark.y, baby_shark.x, now.first, now.second);
// 도달할 수 없는 먹이라면? -> 갱신하지않고 넘어감
if (new_dis == -1) {
continue;
}
// 최단거리라면 타겟을 바꿈
if (new_dis < min_dis) {
min_dis = new_dis;
target.first = now.first;
target.second = now.second;
}
}
// 4. 먹이 먹으러 이동
seconds += min_dis; // 이동 거리만큼 시간 증가
//상어 위치 이동 및 맵 갱신
map[baby_shark.y][baby_shark.x] = 0;
baby_shark.y = target.first;
baby_shark.x = target.second;
map[baby_shark.y][baby_shark.x] = 9;
baby_shark.eaten_fish++;
// 5. 상어 레벨업 체크
if (baby_shark.eaten_fish >= baby_shark.level) {
baby_shark.level++;
baby_shark.eaten_fish = 0;
}
}
cout << seconds;
return 0;
}
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.