백준 3055. 탈출
알고리즘 중급 문제 중 611 - BFS(연습)
1. 간단 설명
고슴도치가 물을 피해 비버집으로 탈출해야한다
고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하는 문제
2. 예시
예제1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3 3
D.*
...
.S.
1초 경과
D**
..*
S..
2초 경과
D**
S**
..*
3초 경과
S**
***
.**
탈출 성공!
이런식으로 탈출에 성공하면 탈출 시간을, 실패하면 문자열을 출력하면 된다
3. 알고리즘
크게 물이 범람하는 과정과, 범람한 맵에서 고슴도치가 이동하는 과정으로 구분할 수 있다
두가지 과정을 각각의 BFS큐에 넣고 돌려주면 된다
또한, 물이 범람하고 고슴도치가 이동하느냐, 고슴도치가 이동하고 물이 범람하느냐
어느것을 먼저 진행하느냐도 매우 중요하다
결론만 먼저 말하면 고슴도치를 이동시키고 물이 범람하는 경우에는,
고슴도치가 물에 빠지는 경우가 발생할 수 있다
예를들어 다음과 같은 경우가 있다
(0,0)은 탈출구 (1,1)은 물, (2,2)에는 고슴도치가 있는 경우
고슴도치가 이동하고, 물을 범람시켜버리면
다음과 같이 고슴도치가 물에 빠져버린다
고슴도치가 곧 물이 찰 칸으로 이동해버리는 상황이 발생하는 것!
그러므로 순서는
물이 먼저 범람하고
고슴도치가 이동한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. R, C 입력 받고, 맵 정보를 입력받는다
1-1. 맵 정보를 입력받으면서 해당 칸이 물('*')이라면, 홍수용 BFS 큐에 추가한다
1-2. 해당 칸이 고슴도치라면 고슴도치용 큐에 추가한다
2. 고슴도치 큐가 빌때까지 BFS를 돌린다
2-1. 물을 범람시킨다
2-1-1. 홍수용 BFS큐에서 맨 앞 노드를 뺀다
2-1-2. 다음칸이 빈칸('.')이라면, 물로 덮는다
2-1-3. 넣은 칸을 큐에 넣는다
2-2. 고슴도치가 이동한다
2-2-1. 고슴도치의 큐에서 맨 앞 노드를 뺀다
2-2-2. 고슴도치가 비버 굴에 도착했는지 체크한다
- 만약 도착했다면, 몇초만에 도달했는지 출력한다
2-2-3. 다음 이동 가능한 칸을 체크한다
- 맵 밖인지, 돌이나 물인지, 이미 이동한곳인지 체크
- 아니라면 이동 가능하므로 큐에 추가한다
3. BFS 리턴값을 확인하고 결과를 출력한다
4. 소스코드
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
#include <iostream>
#include <queue>
using namespace std;
int R, C;
char map[51][51];
int visited[51][51];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct pos {
int y;
int x;
};
queue<pos> flood_qu, hedgehog_qu; // 큐를 2개를 이용한다.
void Input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> R >> C;
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
cin >> map[y][x];
if (map[y][x] == 'S') {
hedgehog_qu.push({ y,x });
visited[y][x] = 1;
}
else if (map[y][x] == '*') {
flood_qu.push({ y,x });
}
}
}
}
int BFS() {
while (!hedgehog_qu.empty()) {
// 1. 물 범람
// while(!qu.empty())가 아닌, 해당 레벨의 원소 수 만큼만 확인함
int water_size = flood_qu.size();
for (int i = 0; i < water_size; i++) {
pos now = flood_qu.front();
flood_qu.pop();
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 >= R || dx >= C)continue;
if (map[dy][dx] == '.') {
map[dy][dx] = '*';
flood_qu.push({ dy,dx });
}
}
}
// 2. 고슴도치 런
// 마찬가지로 해당 레벨만 체크한다
int hedgehog_size = hedgehog_qu.size();
for (int i = 0; i < hedgehog_size; i++) {
pos now = hedgehog_qu.front();
hedgehog_qu.pop();
if (map[now.y][now.x] == 'D') {
return visited[now.y][now.x] - 1;
}
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 >= R || dx >= C)continue;
if (map[dy][dx] == 'X' || map[dy][dx] == '*') continue; // 돌이거나 물이거나
if (visited[dy][dx] != 0) continue; // 방문한적 있다면 패스
visited[dy][dx] = visited[now.y][now.x] + 1;
hedgehog_qu.push({ dy,dx });
}
}
}
return -1;
}
int main() {
Input();
int res = BFS();
if (res == -1) {
cout << "KAKTUS";
}
else {
cout << res;
}
return 0;
}
BFS 문제를 풀면서 동시에 두개의 BFS를 돌린 문제는 이번이 처음이였다
첫 시도는 두가지 경우를 타입을 나누어 한 큐에 넣고 돌렸으나 실패했다
이를 해결하고자 큐 두개로 나누어 돌렸으나,
BFS탐색을 끝날때까지 while(!qu.empty())를 사용해서 맵이 물 전체로 덮이고 나서야
고슴도치가 이동하는 문제가 발생했다
이 문제를 통해서 두개의 BFS를 돌려야할 경우,
해당 레벨만큼의 원소를 BFS수행 해야할 때
while을 사용하지 않고 어떻게 처리해야하는지를 배울 수 있었다