https://www.acmicpc.net/problem/14497
bfs에서도 최단 거리를 구하는 문제를 풀 때
꽤 많은 분들이 거리를 queue에 같이 포함시켜서 푸시는걸 본적 있습니다.
이 문제는 점프의 최소 횟수를 구하는 문제로, 최단 거리를 구하는 문제와 비슷하다고 할 수 있습니다.
사실 이 문제를 이해하는데 꽤 오랜 시간이 걸렸었는데 문제에서 보여주는 예시와 힌트를 보고는 뇌정지가 왔었습니다.
쉽게 얘기한다면 그냥 0인 좌표들을 탐색으로 쭉 지나가다가 1이 만나면 멈춘다고 생각하시면 될것 같습니다.
위에서 언급한것처럼 점프 횟수를 queue에 넣어서 구현할 수도 있겠지만 똑같은 queue를 하나더 사용한다면 그렇게 하지 않고도 해결할 수 있었습니다.
우선 q에는 값이 0인 좌표들만 들어가게 되고, next에는 값이 1인 좌표들이 들어가게 됩니다.
q에 있는 좌표들로 탐색을 쭉 진행하게 되면 그게 1사이클이 되겠고,
다음 next에 있는 원소들을 q에 넣어준다면 다음 사이클을 진행할 수 있습니다.
그렇게 한다면 목적지에 도착했을 때 그 사이클 번호가 답이 될 것입니다.
그 외 로직은 간단하게 bfs 탐색을 1을 만날때까지 해주시면 됩니다.
1을 만난다면 그 좌표의 값은 0으로 바꿔주시면 되겠고, (ex, ey) 에 도착했을 때 t를 리턴하도록 합니다.
|
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
|
#include <iostream>
#include <queue>
#define MAX 310
using namespace std;
typedef pair<int, int> pii;
char list[MAX][MAX];
bool visit[MAX][MAX];
int direct[4][2] = { { 0,1 }, { 1,0 }, { 0,-1 }, { -1,0 } };
int N, M;
int sx, sy, ex, ey;
int bfs() {
queue<pii> q;
q.push({sx,sy});
visit[0][0] = true;
for (int t = 0; !q.empty(); t++) {
queue<pii> next;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == ex && y == ey) return t;
for (int d = 0; d < 4; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (nx <= 0 || ny <= 0 || nx > N || ny > M) continue;
if (visit[nx][ny]) continue;
visit[nx][ny] = true;
if (list[nx][ny] == '0') {
q.push({ nx,ny });
}
if (list[nx][ny] == '1' || list[nx][ny] == '#') {
list[nx][ny] = '0';
next.push({ nx,ny });
}
}
}
while (!next.empty()) {
q.push(next.front());
next.pop();
}
}
return -1;
}
void func() {
cout << bfs() << '\n';
}
void input() {
cin >> N >> M >> sx >> sy >> ex >> ey;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 2310 어드벤처 게임 (0) | 2024.06.25 |
|---|---|
| boj 2412 암벽 등반 (0) | 2024.06.22 |
| boj 2132 나무 위의 벌레 (0) | 2024.06.17 |
| boj 16985 Maaaaaaaaaze (0) | 2022.12.16 |
| boj 14466 소가 길을 건너간 이유 6 (0) | 2022.10.13 |