BOJ - 5427 - 불
문제
문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- ’.’: 빈 공간
- ’#’: 벽
- ’@’: 상근이의 시작 위치
- ‘*’: 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 “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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
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;
// q
queue<pair<int, int>> fq;
queue<pair<int, int>> jq;
vector<string> v;
int main()
{
int num;
cin >> num;
for(int k=0; k < num; k++)
{
cin >> m >> n;
// map 이진화
for(int i=0; i < n; i++)
{
string str;
cin >> str;
for(int j=0; j < m; j++)
{
char tmp = str[j];
if(tmp == '#')
map[i][j] = 1;
else if(tmp == '.')
map[i][j] = 0;
else if(tmp == '@')
{
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;
long long min = 9999999999;
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 != 9999999999)
v.push_back(to_string(min));
else
v.push_back("IMPOSSIBLE");
for(int i=0; i < n+4; i++)
for(int j=0; j < m+4; j++)
{
Fvisited[i][j] = 0;
Jvisited[i][j] = 0;
map[i][j] = 0;
}
// 초기화
while(jq.size())
jq.pop();
while(fq.size())
fq.pop();
}
for(auto &el : v)
cout << el << endl;
return 0;
}
SOL
- map 이진화
- 불, 이동경로 BFS를 각각 따로 생성
- 불 BFS 실행 후 이동경로 BFS 실행
- 불, 이동경로의 visited를 비교 후 동일 좌표에서 불 보다 큰 값을 가지고 있으면 0으로 초기화.
- map의 가장자리를 모두 탐색하여 최솟 값 추출
- 없다면 IMPOSSIBLE 출력
- 지난번에 풀었던 불! 문제와 동일함.