오늘 두번째로 풀어본 문제는 BOJ 4179 불! 이다. 건방지게 덤볐다가 생각보다 겁나 오래 걸렸다 ㅎ,,
BOJ 4179 불!
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입출력
[입력]
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
- #: 벽
- .: 지나갈 수 있는 공간
- J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
- F: 불이 난 공간
J는 입력에서 하나만 주어진다.
[출력]
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
나의 풀이
아아아 풀어도 찝찝한 문제다,,!
평범한 그래프 탐색 문제 같아 보이지만 고려해야 할 부분이 여러개가 있는 문제이다. 골드 4 문제였으니까 뭐,, 그러겠징,,
올라와있던 질문들 처럼 나도 불을 먼저 확인할지,, 지훈이가 먼저갈지가 참 어려웠다,, 이게 머릿속으로는 되지만 배열 상에 표시를 해 주어야 하기때문에 갈 수 있는지 없는지에 대한 조건이 필요했기 때문이다.
그냥 속으로 그어가며 생각해 봤을 때 불이 번지더라도 지훈이가 그 전에 해당 칸에 있다면 지훈이는 지나갈 수 있다. 결국 시간적으로 앞서기만 하면 되기 때문에 불과 지훈이가 지나가는 시간을 각각 계산해 두 배열 fire_sec jihoon_sec 에 기록 해 주었다.
다만 불은 지훈이가 있어도 번질 수 있지만 지훈이는 불이 번져있는 곳이라면 지나갈 수 없기 때문에 불이 번지는 시뮬레이션, bfs 를 통해 먼저 배열 fire_sec 를 완성시키고
이후에 지훈이가 지나가려는 칸을 기준으로, 불이 오는 시간 보다 지훈이가 가는 시간이 빠르면 지나갈 수 있도록 하였다.
여기서 한가지 실수를 한 것이 불이 번지지 않고 갇혀있을 수 있기 때문에 지훈이가 가려는 칸에 불이 번진적 없는 경우도 고려해 주어야 한다는 것을 놓쳤었다 ..! ㅜ
코드
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
// boj 4179 불! , 골드 4
using namespace std;
int MINTIME;
int R, C;
vector<vector<char>> map;
vector<vector<int>> fire_sec;
vector<vector<int>> jihoon_sec;
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
void fire_bfs(queue<pair<int, int>> fire){
while (!fire.empty()){
pair<int, int> curr = fire.front();
fire.pop();
for (int i = 0; i < 4; ++i) {
int nr = curr.first + dy[i];
int nc = curr.second + dx[i];
if (nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc] != '#' && fire_sec[nr][nc] == -1){
fire_sec[nr][nc] = fire_sec[curr.first][curr.second] + 1;
fire.push(make_pair(nr, nc));
}
}
}
}
bool escapable(pair<int, int> start){
bool possible = false;
queue<pair<int, int>> points;
points.push(start);
while (!points.empty()){
pair<int, int> curr = points.front();
points.pop();
for (int i = 0; i < 4; ++i) {
int nr = curr.first + dy[i];
int nc = curr.second + dx[i];
if (nr<0 || nr>=R || nc<0 || nc>=C){
if(!possible) possible = true;
if (MINTIME > jihoon_sec[curr.first][curr.second] + 1){
MINTIME = jihoon_sec[curr.first][curr.second] +1;
}
continue;
}
if (jihoon_sec[nr][nc] != -1 || map[nr][nc] == '#') continue;
if (fire_sec[nr][nc] == -1 || (fire_sec[nr][nc] != -1 && fire_sec[nr][nc] > jihoon_sec[curr.first][curr.second] + 1)){
jihoon_sec[nr][nc] = jihoon_sec[curr.first][curr.second] + 1;
points.push(make_pair(nr, nc));
}
}
}
return possible;
}
int main() {
cin>>R>>C;
MINTIME = INT_MAX;
map.assign(R, vector<char>(C));
fire_sec.assign(R, vector<int>(C,-1));
jihoon_sec.assign(R, vector<int>(C, -1));
pair<int, int> start;
queue<pair<int,int>> fire;
for (int i = 0; i < R; ++i) {
string row;
cin>>row;
for(int j = 0; j < C; j++){
map[i][j] = row[j];
if (map[i][j] == 'J'){
start = make_pair(i, j);
jihoon_sec[i][j] = 0;
} else if (map[i][j] == 'F'){
fire.push(make_pair(i, j));
fire_sec[i][j] = 0;
}
}
}
if (start.first == 0 ||start.first == R-1 || start.second == 0|| start.second == C-1){
MINTIME = 1;
cout<<MINTIME;
}else{
fire_bfs(fire);
if (escapable(start)){
cout<<MINTIME;
}else{
cout<<"IMPOSSIBLE";
}
}
return 0;
}