[BOJ/C++] 백준 4179번: 불!

 

🔗 문제 링크 : https://www.acmicpc.net/problem/4179

 

 

☁ J가 1개랬지, F가 1개라고는 안 했지요😭

 

다양한 테스트케이스에선 통과를 했지만, 채점만 하면 자꾸 틀렸다고 한다. 

원인은... J와 F가 각각 하나만 주어질거라고 생각했던 것이다.

문제에  "J는 입력에서 하나만 주어진다."라는 문장이 있는데, 이걸 보고 F가 여러 개일 경우도 생각해봤어야 했다.

작성해 놓은 코드에서 수정이 많이 필요하진 않았지만, 일찍 깨닫지 못한 나에게.. 분노했다.🧨

 

똑바로 읽어!!! 그리고 생각해!!!

 

 

 

---

 

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야 한다.

지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

 

 

 

 

입출력 예시

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

 

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

 

 

입출력 예시

 

 

 

---

 

풀이 

BFS를 두 번 이용했다.

처음 한 번은 불이 확산해서 각 칸에 도달하는 시간을 알아내고,

다른 한 번은 지훈이가 접근할 수 있는 칸을 탐색한다.

 

/* 불 확산 */

BFS를 이용하여, 불이 각 칸에 도달하는 데 걸리는 시간(초)을 간단하게 알아낼 수 있다..

 

 

/* 탈출 시도 */

지훈이가 성공적으로 탈출했다고 판단할 수 있는 조건은 아래와 같다.

if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
    cout << map_jh[curr.x][curr.y] + 1;
    return 0;
}

즉, 현재 칸에서 접근가능한(Queue에서 뽑아낸) 다음 칸의 좌표가 미로 범위를 벗어날 때이다.

탈출에 성공했으면, 탈출에 걸린 시간을 출력하고 프로그램을 종료한다.

• 탈출에 걸린시간 : 다음 칸의 좌표가 탈출 성공 조건을 만족하였기 때문에, 현재 칸에 도달하는 데 걸린 시간에서 +1을 해준다.

 

Queue에 들어가는 좌표는 아래와 같은 조건으로 판별하여, 현재 칸에서 접근 가능한  인접좌표만 push 된다.

if (map[nx][ny] == '#' || map_jh[nx][ny] != -1) continue; 
if (map_fire[nx][ny] != -1 && map_fire[nx][ny] <= map_jh[curr.x][curr.y] + 1) continue;

 

• 벽이 아니어야 한다.
• 방문한 적이 없어야 한다.
• 불이 확산될 수 있는 칸이면, 불보다 먼저 도착할 수 있어야 한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

struct Pos {
    Pos (int x, int y) {
        this->x = x;
        this->y = y;
    }
    int x;
    int y;
};

int main() {
    ios_base::sync_with_stdio(0);
    Pos jhStartPos(0, 0);
    queue<Pos> q;
    cin >> R >> C;

    vector<vector<char>> map(R, vector<char>(C, ' '));
    vector<vector<int>> map_fire(R, vector<int>(C, -1)); 
    vector<vector<int>> map_jh(R, vector<int>(C, -1)); 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'F') {
                q.push(Pos(i, j));
                map_fire[i][j] = 0;
            }
            else if (map[i][j] == 'J') {
                jhStartPos = Pos(i, j);
                map_jh[i][j] = 0;
            }
        }
    }

    /* 불 확산 */
    while (!q.empty()) {
        Pos curr = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = curr.x + dirX[dir];
            int ny = curr.y + dirY[dir];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if (map[nx][ny] == '#' || map_fire[nx][ny] != -1) continue;
            q.push(Pos(nx, ny));
            map_fire[nx][ny] = map_fire[curr.x][curr.y] + 1;
        }
    }

    /* 탈출 시도 */
    q.push(jhStartPos);
    while (!q.empty()) {
        Pos curr = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = curr.x + dirX[dir];
            int ny = curr.y + dirY[dir];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                cout << map_jh[curr.x][curr.y] + 1;
                return 0;
            }
            if (map[nx][ny] == '#' || map_jh[nx][ny] != -1) continue; 
            if (map_fire[nx][ny] != -1 && map_fire[nx][ny] <= map_jh[curr.x][curr.y] + 1) continue;
            q.push(Pos(nx, ny));
            map_jh[nx][ny] = map_jh[curr.x][curr.y] + 1;
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

 

 

 

---