문제 링크 : https://www.acmicpc.net/problem/4179
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자
www.acmicpc.net
풀이
BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다.
골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다.
#include <iostream>
#include <queue>
#include <utility>
#define X first
#define Y second
using namespace std;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
string brd[1002];
int fire_dist[1002][1002];
int jh_dist[1002][1002];
queue<pair<int,int> > Qj;
queue<pair<int,int> > Qf;
int r, c; // r = 행, c = 열
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> r >> c;
for(int i = 0; i < r; i++){ // 미로 저장
string str;
cin >> str;
brd[i] = str;
for(int j = 0; j < c; j++){
if(brd[i][j] == 'F'){ // 불의 시작점 저장
Qf.push({i,j});
fire_dist[i][j] = 1;
}
if(brd[i][j] == 'J'){ // 지훈이의 시작점 저장
Qj.push({i,j});
jh_dist[i][j] = 1;
}
}
}
while(!Qf.empty()){ // 불이 붙는 시간 계산
auto cur = Qf.front();
Qf.pop();
int prev = fire_dist[cur.X][cur.Y]; // 불이 붙은 시간
for(int i = 0; i < 4; i++){
int x = cur.X + dx[i];
int y = cur.Y + dy[i];
if(x >= 0 && x < r && y >= 0 && y < c){ // 유효성 검사
// 다음 칸이 불이 붙을 수 있는 공간(.,J)이면
if(brd[x][y] == 'J' or brd[x][y] == '.'){
if(fire_dist[x][y] == 0){ // 아직 불이 붙지 않았다면
Qf.push({x,y}); // 1분 후에 불이 붙을 장소를 큐에 저장
fire_dist[x][y] = prev + 1; // 1분 후 다음 칸에 불이 붙음을 저장
}else{ // 이미 불이 붙은 장소라면
if(fire_dist[x][y] > prev + 1){ // 더 빨리 불이 붙을 수 있는 장소였는지 체크 후
Qf.push({x,y}); // 재계산을 위해 큐에 저장
fire_dist[x][y] = prev + 1; // 1분 후 다음 칸에 불이 붙음을 저장
}
}
}
}
}
}
while(!Qj.empty()){ // 지훈이가 도착하는 시간 계산
auto cur = Qj.front();
Qj.pop();
if(cur.X == 0 or cur.X == r-1 or cur.Y == 0 or cur.Y == c-1){ // 지훈이의 시작점이 애초에 가장자리이면 바로 탈출
cout << 1;
return 0;
}
int prev = jh_dist[cur.X][cur.Y]; // 칸에 도착한 시간
for(int i = 0; i < 4; i++){
int x = cur.X + dx[i];
int y = cur.Y + dy[i];
if(x >= 0 && x < r && y >= 0 && y < c){ // 유효성 검사
// 다음 칸이 지나갈 수 있는 공간(.)이면서 방문을 안 했으면서 불이 붙기 전에 도착할 수 있는 칸이거나 불이 붙이 않지 않았다면 도착할 수 있는 시간 계산
if(brd[x][y] == '.' && (prev + 1 < fire_dist[x][y] or fire_dist[x][y] == 0) && jh_dist[x][y] == 0){
jh_dist[x][y] = prev + 1; // 1분 후 해당 칸에 도착할 수 있음을 저장
if(x == r-1 or y == c-1 or x == 0 or y == 0){ // 탈출 성공
cout << jh_dist[x][y]; // 다음 번에 탈출하는 것이지만 시작이 1이었으므로 그대로 출력
return 0;
}
Qj.push({x,y}); // 1분 후에 도착할 장소를 큐에 저장
}
}
}
}
cout << "IMPOSSIBLE";
}
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
(C++) 백준 1629번 - 곱셈 (0) | 2023.04.01 |
---|---|
(C++) 백준 1697번 - 숨바꼭질 (0) | 2023.04.01 |
(C++) 백준 7576번 - 토마토 (0) | 2023.03.30 |
(C++) 백준 2178번 - 미로 탐색 (0) | 2023.03.29 |
(C++) 백준 1926번 - 그림 (0) | 2023.03.29 |