https://www.acmicpc.net/problem/4179
문제풀이
지훈이가 탈출할 수 있는 가장 빠른시간을 구해야한다 문제를 보자마자 bfs로 접근이 필요한 것을 확신할 수 있다 단 4방향으로 퍼지는 불을 생각해야 한다 4방향으로 퍼지는 불 + 불은 여러개가 있을 수 있음에서 결국 문제를 해결하지 못했다.
첫번쨰로 지훈이가 불을 피해서 도망갈 수 있는경우와 그렇지 못한 경우를 생각해야 한다 불이 퍼지는 최단거리와 지훈이가 탈출하는 최단거리 테이블을 비교하여 지훈이의 위치가 불의 위치보다 빠르다면 지훈이는 해당 위치로 도망갈 수 있다.
지훈이의 시작위치 -> 0, 0
불의 시작위치 -> 0, 1
0(J) 1(F) | 0(F) 1(J) |
1(J) 2(F) -> 이동가능 | 2(J) 1(F) -> 이동불가(이미 불이번짐) |
2(J) 3(F) -> 이동가능 | 3(J) 2(F) -> 이동불가 |
표처럼 만약 지훈이가 이동하려는 위치가 이미 불이 번진상태임을 bfs에서 이동하기 전에 체크해주면 된다.
void find_exit(queue<pair<int, int>> q){
while(q.size()){
tie(y, x) = q.front(); q.pop();
if(y == 0 || x == 0 || y == r - 1 || x == c - 1){
ret = person[y][x];
break;
}
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
if(person[ny][nx]) continue;
if(a[ny][nx] == '#') continue;
if(person[y][x] + 1 >= fire[ny][nx]) continue;
person[ny][nx] = person[y][x] + 1;
q.push({ny, nx});
}
}
return;
}
person[y][x] + 1 이동하려는 위치의 값이 불의 최단거리와 같거나 크다면 이동을 하지 않도록 처리해준다. 만약 이동이 가능하다면 최단거리를 갱신해주면 된다.
정답코드
#include <bits/stdc++.h>
using namespace std;
const int INF = 99999999;
int r, c, sy, sx, person[1001][1001], fire[1001][1001], ret, y, x;
char a[1001][1001];
int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1};
void spread_fire(queue<pair<int, int>> q){
while(q.size()){
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 < 0 || nx < 0 || ny >= r || nx >= c) continue;
if(fire[ny][nx] != INF || a[ny][nx] == '#') continue;
fire[ny][nx] = fire[y][x] + 1;
q.push({ny, nx});
}
}
return;
}
void find_exit(queue<pair<int, int>> q){
while(q.size()){
tie(y, x) = q.front(); q.pop();
if(y == 0 || x == 0 || y == r - 1 || x == c - 1){
ret = person[y][x];
break;
}
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
if(person[ny][nx]) continue;
if(a[ny][nx] == '#') continue;
if(person[y][x] + 1 >= fire[ny][nx]) continue;
person[ny][nx] = person[y][x] + 1;
q.push({ny, nx});
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> r >> c;
queue<pair<int, int>> q;
fill(&fire[0][0], &fire[0][0] + 1001 * 1001, INF);
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
cin >> a[i][j];
if(a[i][j] == 'J'){sy = i; sx = j;}
if(a[i][j] == 'F'){
fire[i][j] = 1;
q.push({i, j});
}
}
}
spread_fire(q);
person[sy][sx] = 1;
queue<pair<int, int>> q2;
q2.push({sy, sx});
find_exit(q2);
if(ret != 0) cout << ret << '\n';
else cout << "IMPOSSIBLE" << '\n';
return 0;
}
조금 귀찮더라도 코드가 길어져서 헷갈리기 때문에 일부러 2개의 함수를 만들어서 처리했다
아직은 골드 문제는 정답이나 힌트를 안보고 풀기는 어렵다 하지만 풀면서 경험치가 쌓이는 기분이다.
'알고리즘' 카테고리의 다른 글
[BOJ/DFS] BOJ 1068 트리 C++ (0) | 2023.12.08 |
---|