이번에는 백준 4179번 불! 문제를 풀어보았습니다.
처음에는 지훈이를 DFS로 이동시키면서 매 시간마다 불도 함께 확산시키는 방식으로 구현해보았습니다.
하지만 불의 상태를 계속 저장하고 복구해야 했고, 탐색해야 하는 경우의 수도 많아져 효율적으로 해결하기 어려웠습니다.
이후에는 불도 최단 거리로 퍼지고, 지훈이도 최단 거리로 이동한다는 점에 주목하여 BFS를 이용해 다시 구현하였습니다.
먼저 불이 각 위치에 도착하는 최단 시간을 구한 뒤, 지훈이가 그보다 먼저 도착할 수 있는 위치만 이동하도록 처리하였습니다.
문제 설명
미로에는 지훈이와 불이 존재합니다.
지훈이와 불은 매 분마다 상하좌우로 한 칸씩 이동합니다.
불은 매 시간마다 인접한 칸으로 확산됩니다.
지훈이는 미로의 가장자리에 도착하면 탈출할 수 있습니다.
지훈이가 불보다 먼저 탈출할 수 있는지, 그리고 가능하다면 가장 빠른 탈출 시간을 구하는 문제입니다.
풀이 아이디어
V1
처음에는 DFS를 이용하여 지훈이를 이동시키면서 불도 함께 이동시키는 방식으로 구현하였습니다.
현재 시간에 존재하는 불들을 먼저 확산시키고, 이후 지훈이가 이동하도록 하였습니다.
DFS가 종료되어 되돌아올 때는 새롭게 확산된 불들을 다시 제거하여 원래 상태로 복구하였습니다.
이 과정을 반복하면서 가장자리까지 도달 가능한 경우 최단 탈출 시간을 갱신하였습니다.
V2
다시 생각해보니 불이 이동하는 과정도 결국 최단 거리 탐색이고, 지훈이 역시 최단 거리로 이동하는 문제였습니다.
따라서 먼저 BFS를 이용하여 불이 각 위치에 도착하는 최단 시간을 모두 구하였습니다.
이후 지훈이에 대해서 BFS를 수행하면서, 불보다 먼저 도착할 수 있는 위치만 이동하도록 구현하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
int min_exit = INT_MAX;
vector<vector<int>> inp_map;
vector<vector<int>> fires_map;
vector<vector<pair<int,int>>> fires;
vector<vector<int>> visited;
bool can_exit = false;
void fire_flood(int level) {
for (int f=0; f<fires[level].size(); f++) {
int y = fires[level][f].first;
int x = fires[level][f].second;
fires_map[y][x] = 1;
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 && inp_map[ny][nx] != 0 && inp_map[ny][nx] != 2) {
fires_map[ny][nx] = 1;
fires[level+1].push_back(make_pair(ny,nx));
}
}
}
}
void return_flood(int level) {
for (int f=0; f<fires[level].size(); f++) {
fires_map[fires[level][f].first][fires[level][f].second] = 0;
}
}
void dfs(int y, int x, int level) {
if (y == N-1 || x == M-1 || y == 0 || x == 0) {
can_exit = true;
min_exit = min(min_exit, level);
return;
}
visited[y][x] = 1;
fires.push_back(vector<pair<int,int>>());
fire_flood(level);
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 && inp_map[ny][nx] != 0) {
if (inp_map[ny][nx] == 1 && visited[ny][nx] == 0) {
dfs(ny, nx, level+1);
}
}
}
return_flood(level+1);
fires.pop_back();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fires.push_back(vector<pair<int,int>>());
cin >> N;
cin >> M;
int sty, stx;
for (int i=0; i<N; i++) {
inp_map.push_back(vector<int>());
fires_map.push_back(vector<int>(M,0));
visited.push_back(vector<int>(M,0));
string temp;
cin >> temp;
for (int j=0; j<M; j++) {
if (temp[j] == '#')
inp_map[i].push_back(0);
else if (temp[j] == 'F') {
inp_map[i].push_back(2);
fires[0].push_back(make_pair(i,j));
} else if (temp[j] == 'J') {
inp_map[i].push_back(3);
sty = i;
stx = j;
} else
inp_map[i].push_back(1);
}
}
dfs(sty,stx,0);
if (can_exit) cout << min_exit+1;
else cout << "IMPOSSIBLE";
return 0;
}V1 풀이 흐름
- 입력을 받으면서 벽, 불, 지훈이 위치를 저장합니다.
- DFS를 이용하여 지훈이를 이동시킵니다.
- 지훈이가 이동하기 전에 현재 존재하는 불들을 먼저 확산시킵니다.
- 새롭게 확산된 불들을 다음 level에 저장합니다.
- DFS가 종료되어 되돌아갈 때는 저장된 불 위치를 이용하여 원래 상태로 복구합니다.
- 지훈이가 가장자리에 도착하면 탈출 가능 여부를 갱신합니다.
- 모든 경로를 탐색한 뒤 최소 탈출 시간을 출력합니다.
V1 구현 포인트
1. 시간별 불의 위치 저장
DFS가 종료될 때 원래 상태로 되돌려야 했기 때문에 시간별로 불의 위치를 저장하였습니다.
fires.push_back(vector<pair<int,int>>());새롭게 생성된 불들을 다음 level에 저장하였습니다.
2. 불 확산
현재 시간에 존재하는 불들을 기준으로 다음 시간의 불을 생성하였습니다.
fire_flood(level);상하좌우 방향으로 확산 가능한 위치를 모두 저장하였습니다.
3. 상태 복구
DFS 백트래킹 과정에서 불 상태를 원래대로 되돌렸습니다.
return_flood(level+1);저장해두었던 불 위치를 이용하여 복구하였습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
vector<vector<char>> inp_map;
int fires[1004][1004];
int human[1004][1004];
queue<pair<int,int>> q;
int ret, sty,stx;
int max_val = INT_MAX;
int main() {
cin >> N >> M;
fill(&fires[0][0], &fires[0][0] + 1004 * 1004, max_val);
for (int i = 0; i < N; i++) {
string s;
cin >> s;
inp_map.push_back(vector<char>());
for (int j = 0; j < M; j++) {
if (s[j] == 'J') {
inp_map[i].push_back(s[j]);
sty = i, stx = j;
} else if (s[j] == 'F') {
fires[i][j] = 1;
inp_map[i].push_back(s[j]);
q.push(make_pair(i,j));
} else {
inp_map[i].push_back(s[j]);
}
}
}
while(!q.empty()) {
int y, x;
tie(y,x) = q.front();
q.pop();
for (int i=0; i<4; i++) {
int ny = y+dy[i];
int nx = x+dx[i];
if (ny >= N || nx >= M || ny < 0 || nx < 0) continue;
if (fires[ny][nx] != max_val || inp_map[ny][nx] == '#') continue;
fires[ny][nx] = fires[y][x] + 1;
q.push(make_pair(ny,nx));
}
}
human[sty][stx] = 1;
q.push(make_pair(sty,stx));
while(!q.empty()) {
int y,x;
tie(y,x) = q.front();
q.pop();
if (y == N-1 || x == M-1 || y == 0 || x == 0) {
ret = human[y][x];
break;
}
for (int i=0; i<4; i++) {
int ny = y+dy[i];
int nx = x+dx[i];
if (ny >= N || nx >= M || ny < 0 || nx < 0) continue;
if (human[ny][nx] || inp_map[ny][nx] == '#') continue;
if (fires[ny][nx] <= human[y][x] + 1) continue;
human[ny][nx] = human[y][x] + 1;
q.push(make_pair(ny,nx));
}
}
if (ret == 0) cout << "IMPOSSIBLE";
else cout << ret;
return 0;
}V2 풀이 흐름
- 모든 불의 시작 위치를 큐에 넣습니다.
- BFS를 수행하여 각 위치에 불이 도착하는 최단 시간을 구합니다.
- fires 배열에 불의 도착 시간을 저장합니다.
- 이후 지훈이에 대해 BFS를 수행합니다.
- 불보다 늦게 도착하거나 같은 시간에 도착하는 위치는 이동하지 않습니다.
- 가장자리에 도착하면 탈출 시간을 저장합니다.
- 탈출 가능 여부를 출력합니다.
V2 구현 포인트
1. 불의 최단 거리 먼저 계산
모든 불을 시작점으로 BFS를 수행하였습니다.
if (s[j] == 'F') {
fires[i][j] = 1;
q.push(make_pair(i,j));
}여러 시작점에서 동시에 BFS를 수행하는 형태입니다.
2. 불 도착 시간 저장
불이 각 위치에 도착하는 시간을 fires 배열에 저장하였습니다.
fires[ny][nx] = fires[y][x] + 1;이 값은 이후 지훈이 이동 가능 여부를 판단하는 기준으로 사용됩니다.
3. 불보다 먼저 도착 가능한 경우만 이동
이 문제의 핵심이었던 부분입니다.
if (fires[ny][nx] <= human[y][x] + 1) continue;불이 먼저 도착하거나 같은 시간에 도착하는 위치는 이동하지 않았습니다.
4. 가장자리 도착 시 탈출
현재 위치가 가장자리라면 탈출 가능한 상태입니다.
if (y == N-1 || x == M-1 || y == 0 || x == 0)BFS는 최단 거리를 보장하므로 가장 먼저 도착한 시간이 정답이 됩니다.
