https://www.acmicpc.net/problem/4179
4179번: 불!
문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간
www.acmicpc.net
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력하는 BFS문제이다.
3055번 탈출 문제(문제 링크)랑 비슷한 것 같다.
탈출 문제에서는 물이 퍼지는 시간을 먼저 BFS로 저장해놓고, 고슴도치가 이동할 곳의 시간이 물이 퍼진시간보다 작은 경우에만 이동할 수 있도록 구현했다. (문제 풀이 링크)
이번에도 똑같이 풀어봤는데 정답은 뜨지만 메모리를 많이 써서 다른 방법으로 다시 풀어봤다.
먼저 지훈이가 이동할 좌표와 불이 확산될 좌표를 각각 다른 큐에 넣어놓고 이동시킨다.
그리고 매분마다 불을 먼저 이동시키고 지훈이를 이동시키면 불이 확산되지 않은 곳으로 이동할 수 있다.
(입력받을 때 지훈이의 위치는 지나갈 수 있는 공간이므로 '.'으로 바꿔줘야 한다.)
미로를 탈출하는 경우는 입력으로 주어지는 지도 밖으로 벗어나는 경우이므로
배열의 크기를 더 크게 잡아서 범위를 벗어나는 경우에 탈출한 것으로 본다.
아래 그림처럼 지도를 (1, 1)부터 입력받으면 지훈이의 위치가 0행이거나 0열이거나 R+1행이거나 C+1 열인 경우 미로를 탈출한다.
BFS를 진행할 때에는, 먼저 지훈이가 이동할 수 있는 곳이 더 없다면 끝나기 때문에 지훈이의 좌표를 담은 큐가 비었다면 BFS를 종료한다. 그리고 매분마다 불을 먼저 확산시키고 다음에 지훈이를 이동시키기 위해서
각자의 큐사이즈만큼씩만 진행하면 된다.
한 번에 이동할 수 있는 위치만큼(현재 위치로부터 1만큼 이동한 곳)이 큐에 새로 들어가기 때문이다.
지훈이가 미로를 탈출했다면 그때의 시간을 출력하고 바로 리턴해서 종료시킨다.
이 부분에서 종료되지 않고 BFS탐색을 끝낸다면 탈출이 불가능한 경우이므로 IMPOSSIBLE을 출력하고 종료한다.
|
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>
using namespace std;
int r, c;
char map[1001][1001];
bool visit[1001][1001];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//불이 이동할 큐
queue<pair<int, int> > fq;
//지훈이 이동할 큐
queue<pair<int, int> > jq;
cin >> r >> c;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> map[i][j];
if (map[i][j] == 'J') {
jq.push(make_pair(i, j));
visit[i][j] = true;
map[i][j] = '.';
}
else if (map[i][j] == 'F') {
fq.push(make_pair(i, j));
visit[i][j] = true;
}
}
}
int x, y;
int time = 0;
while (!jq.empty()) {
int jqsize = jq.size();
int fqsize = fq.size();
int nx, ny;
time++;
//불이 먼저 이동
while (fqsize--) {
x = fq.front().first;
y = fq.front().second;
fq.pop();
for (int k = 0; k < 4; k++) {
nx = x + dx[k];
ny = y + dy[k];
//범위 체크
if (nx <= 0 || ny <= 0 || nx > r || ny > c) continue;
//벽이면 못간다
if (map[nx][ny] == '#') continue;
//방문 체크
if (visit[nx][ny]) continue;
fq.push(make_pair(nx, ny));
visit[nx][ny] = true;
}
}
//지훈이 이동
while (jqsize--) {
x = jq.front().first;
y = jq.front().second;
jq.pop();
for (int k = 0; k < 4; k++) {
nx = x + dx[k];
ny = y + dy[k];
//벽이면 못간다
if (map[nx][ny] == '#') continue;
//이미 이동한 곳이거나, 불이 이미 확산되어 있거나 같은 시간에 확산된다
if (visit[nx][ny]) continue;
//탈출한 경우 바로 종료
if (nx == 0 || ny == 0 || nx == r + 1 || ny == c + 1) {
cout << time << '\n';
return 0;
}
jq.push(make_pair(nx, ny));
visit[nx][ny] = true;
}
}
}
//위에서 종료되지 못한 경우
cout << "IMPOSSIBLE" << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 10757. 큰 수 A + B (0) | 2020.03.10 |
|---|---|
| [BOJ] 1331. 나이트 투어 (0) | 2020.03.03 |
| [BOJ] 1938. 통나무 옮기기 (0) | 2020.02.12 |
| [BOJ] 17780. 새로운 게임 (0) | 2020.02.03 |
| [BOJ] 17837. 새로운 게임 2 (0) | 2020.02.03 |