1. 문제분석
지훈이와 불은 매 분마다 동시에 한칸씩 이동하는데 불은 상하좌우로 한칸씩 이동함
두번째 board 배열과 큐를 만들어서 불이 번지는 시간을 계산하고 세번째 board 배열과 큐를 만들어서 지훈이가 이동하는 최소거리에 불이 붙는지 두번째 board 배열과 비교하면서 계산한다.
지훈이가 **까지 이동할 때 2분이 걸리는데 불은 해당 지점까지 1분이 걸리므로 지훈이가 불이 있는 해당지점의 시간과 같거나 크다면 이동이 불가능하다.
이렇게 하면 시작점이 두 종류인 문제를 풀 수 있는데, 지금 이 방식은 불의 전파는 지훈이의 이동에 영향을 받지 않아서 불만 먼저 전파해서 시간을 계산하는게 가능했다.
그러나 A, B 둘다 서로에게 영향을 준다면 불을 먼저 전파하는데 있어서 지훈이의 이동에 영향을 받기 때문에 지금의 방식으로는 해결할 수 없고 시간 순으로 A와 B를 동시에 이동해야 된다.
2. 코드
#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist_1[1002][1002]; // 불의 전파
int dist_2[1002][1002]; // 지훈이 이동
// 상하좌우
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
// 1.입력
int R, C; // R(행:X), C(열:Y)
cin >> R >> C;
for (int i = 0; i < R; i++) {
cin >> board[i];
}
// 2.로직
queue<pair<int, int>> Q1;
queue<pair<int, int>> Q2;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
dist_1[i][j] = -1;
dist_2[i][j] = -1;
if (board[i][j] == 'F') {
Q1.push({ i, j });
dist_1[i][j] = 0;
}
else if (board[i][j] == 'J') {
Q2.push({ i, j });
dist_2[i][j] = 0;
}
}
}
// 불 전파 BFS
while (!Q1.empty()) {
pair<int, int> cur = Q1.front(); Q1.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
// 벽이 아니면서 불이 없는 지점(-1)만 전파 시킴
if (board[nx][ny] == '#' || dist_1[nx][ny] >= 0) continue;
dist_1[nx][ny] = dist_1[cur.X][cur.Y] + 1;
Q1.push({ nx, ny });
}
}
// 지훈 이동 BFS
while (!Q2.empty()) {
pair<int, int> cur = Q2.front(); Q2.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 미로 탈출(배열의 범위를 벗어난 경우)
if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
cout << dist_2[cur.X][cur.Y] + 1;
return 0;
}
if (board[nx][ny] == '#' || dist_2[nx][ny] >= dist_1[nx][ny]) continue;
dist_2[nx][ny] = dist_2[cur.X][cur.Y] + 1;
Q2.push({ nx, ny });
}
}
cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}
재풀이 코드
#include<iostream>
#include<queue>
using namespace std;
string board[1002];
int fireDis[1002][1002];
int playerDis[1002][1002];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int r, c;
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
// 1.입력
cin >> r >> c;
queue<pair<int, int>> Q1; // 불이 전파되는 시간
queue<pair<int, int>> Q2; // 플레이어의 이동가능 시간
for (int i = 0; i < r; i++) {
cin >> board[i];
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
fireDis[i][j] = -1;
if (board[i][j] == 'J') {
playerDis[i][j] = 0;
Q2.push({ i,j });
}
else if (board[i][j] == 'F') {
fireDis[i][j] = 0;
Q1.push({ i,j });
}
}
}
// 2.로직
// 불이 전파되는 시간 계산
while (!Q1.empty()) {
pair<int, int> cur = Q1.front();
Q1.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue; // 범위를 나간경우 제외
if (board[nx][ny] == '#' || fireDis[nx][ny] >= 0) continue; // 벽이거나 이미 이동이 계산됬으면 제외
fireDis[nx][ny] = fireDis[cur.first][cur.second] + 1;
Q1.push({ nx, ny });
}
}
// 지훈(플레이어)이가 이동가능한 경로 계산
bool impossibleCk = false;
while (!Q2.empty()) {
pair<int, int> cur = Q2.front();
Q2.pop();
// 가장자리에 있는 경우
if (cur.first == 0 || cur.first == r - 1 || cur.second == 0 || cur.second == c - 1) {
impossibleCk = true;
cout << playerDis[cur.first][cur.second] + 1;
return 0;
}
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (board[nx][ny] == '#' || playerDis[cur.first][cur.second] + 1 >= fireDis[nx][ny]) continue;
playerDis[nx][ny] = playerDis[cur.first][cur.second] + 1;
Q2.push({ nx, ny });
}
}
if (!impossibleCk) {
cout << "IMPOSSIBLE";
}
return 0;
}
