반응형
문제 링크: https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
<문제 풀이> BFS, 최단거리
이문제는 모든 물에 대해서(물을 모두 큐에 담으면 됨) BFS로 물에서 모든 정점까지의 최단 거리를 구하고, 고슴 도치에 대해서 똑같이 BFS를 진행하면서 물 보다 더 최단 거리로 이동할 수 있는 경우만 큐에 담으면 됩니다.
주의할 점은 입력으로 물이 없을 수도 있습니다(물이 없으면 물의 visited 최단 거리 배열 값은 -1).
<C++ 소스 코드>
|
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
|
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define X first
#define Y second
int R, C;
char board[50][50];
int visitedW[50][50];
int visitedS[50][50];
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
void wBFS() {
queue<pair<int, int> > Q;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (board[i][j] == '*') {
Q.push({ i, j });
visitedW[i][j] = 0;
}
}
}
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;
if (board[nx][ny] == 'D' || board[nx][ny] == 'X') continue;
if (visitedW[nx][ny] != -1)continue;
Q.push({ nx, ny });
visitedW[nx][ny] = visitedW[cur.X][cur.Y] + 1;
}
}
}
int sBFS() {
int ret = -1;
queue<pair<int, int> > Q;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (board[i][j] == 'S') {
Q.push({ i, j });
visitedS[i][j] = 0;
}
}
}
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;
if (board[nx][ny] == 'X') continue;
if (visitedS[nx][ny] != -1)continue;
if (board[nx][ny] != 'D' && visitedW[nx][ny] != -1 && visitedS[cur.X][cur.Y] + 1 >= visitedW[nx][ny])continue; //물 보다 늦게 도착하면 무시
Q.push({ nx, ny });
visitedS[nx][ny] = visitedS[cur.X][cur.Y] + 1;
if (board[nx][ny] == 'D') {
return visitedS[nx][ny];
}
}
}
return ret;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> board[i][j];
}
}
fill(&visitedW[0][0], &visitedW[49][50], -1);
fill(&visitedS[0][0], &visitedS[49][50], -1);
wBFS();
int res = sBFS();
if (res == -1) cout << "KAKTUS";
else cout << res;
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 15685번] 드래곤 커브 (0) | 2022.03.25 |
|---|---|
| [백준 14890번] 경사로 (0) | 2022.03.16 |
| [백준 16946번] 벽 부수고 이동하기 4 (0) | 2022.03.11 |
| [백준 16234번] 인구 이동 (0) | 2022.03.04 |
| [백준 13460번] 구슬 탈출 2 (0) | 2022.02.10 |
