BOJ - 4179 - 불!
문제
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// map
int n, m;
int map[1004][1004];
int Jvisited[1004][1004];
int Fvisited[1004][1004];
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
// x, y
int x, y, jx, jy, fx, fy;
vector<pair<int, int>> v;
// q
queue<pair<int, int>> fq;
queue<pair<int, int>> jq;
int main()
{
cin >> n >> m;
// map 이진화
for(int i=0; i < n; i++)
for(int j=0; j < m; j++)
{
char tmp;
cin >> tmp;
if(tmp == '#')
map[i][j] = 1;
else if(tmp == '.')
map[i][j] = 0;
else if(tmp == 'J')
{
jy = i;
jx = j;
}
else
{
fq.push({i, j});
Fvisited[i][j] = 1;
}
}
jq.push({jy, jx});
Jvisited[jy][jx] = 1;
// 최단거리
while (fq.size())
{
fx = fq.front().second;
fy = fq.front().first;
fq.pop();
for(int i=0; i < 4; i++)
{
int ny = fy + dy[i];
int nx = fx + dx[i];
if(ny < 0 || nx < 0|| ny >= n || nx >= m)
continue;
// 벽일 경우, 이미 방문 했을 경우
if(map[ny][nx] || Fvisited[ny][nx])
continue;
Fvisited[ny][nx] = Fvisited[fy][fx] + 1;
fq.push({ny, nx});
}
}
while(jq.size())
{
y = jq.front().first;
x = jq.front().second;
jq.pop();
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0|| ny >= n || nx >= m)
continue;
// 벽일 경우, 이미 방문 했을 경우
if(map[ny][nx] || Jvisited[ny][nx])
continue;
Jvisited[ny][nx] = Jvisited[y][x] + 1;
jq.push({ny, nx});
}
}
// 불을 피해가는 최단거리 값
for(int i=0; i < n; i++)
for(int j=0; j < m; j++)
if(Jvisited[i][j] >= Fvisited[i][j] && Fvisited[i][j])
Jvisited[i][j] = 0;
int min = 9999;
for(int i=0; i < n; i++)
{
if(i == 0 || i == n-1)
{
for(int j=0; j < m; j++)
if(min > Jvisited[i][j] && Jvisited[i][j])
min = Jvisited[i][j];
}
else
{
if(min > Jvisited[i][0] && Jvisited[i][0])
min = Jvisited[i][0];
else if(min > Jvisited[i][m-1] && Jvisited[i][m-1])
min = Jvisited[i][m-1];
}
}
// map 출력
// cout << "---------------" << endl;
// for(int i=0; i < n; i++)
// {
// for(int j=0; j < m; j++)
// {
// cout << Jvisited[i][j] << " ";
// }
// cout << endl;
// }
// 출구가 존재하면
if(min != 9999)
cout << min << endl;
else
cout << "IMPOSSIBLE " << endl;
return 0;
}
SOL
- map 이진화
- 불, 이동경로 BFS를 각각 따로 생성
- 불 BFS 실행 후 이동경로 BFS 실행
- 불, 이동경로의 visited를 비교 후 동일 좌표에서 불 보다 큰 값을 가지고 있으면 0으로 초기화.
- map의 가장자리를 모두 탐색하여 최솟 값 추출
- 없다면 IMPOSSIBLE 출력