[C++] 백준/Gold/3055. 탈출

문제: 탈출 (백준 3055번)

문제 분석

출발 지점부터 도착 지점까지 최단 거리를 구하는 문제인데, 매 이동마다 물에 잠기는 구간이 늘어난다. 맵이 물에 잠기는 시간에 따른 시뮬레이션과, 출발 지점부터 도착 지점까지의 이동 경로를 구하는 과정을 따로 처리해야 한다. 언뜻 보면 단순한 시뮬레이션 문제로 보이지만, 실제로는 맵이 물에 잠기는 시간을 계산하는 BFS와, 출발 지점부터 도착 지점까지의 최단 거리를 구하는 BFS를 두 번 수행하면 쉽게 계산할 수 있다.

 

먼저 보드(board)를 입력받는다. 보드는 r×c 크기의 2차원 배열로, 각 칸에 문자('S', 'D', '*', '.', 'X')가 주어진다.

• 'S'는 시작 지점, 'D'는 도착 지점, '*'는 물, 'X'는 바위(갈 수 없는 구역), '.'은 빈 공간이다.

첫 번째 BFS (물 확산)

• 보드에서 물이 있는 모든 칸('*')을 큐에 넣고, 각 칸에 물이 도달하는 시간을 저장하는 2차원 배열(depth)을 초기화한다.
• 물은 매 분마다 상하좌우로 확산되며, 이미 물이 도달한 칸보다 늦게 도달하는 경우는 업데이트하지 않는다.

두 번째 BFS (탈출 경로 탐색)

• 시작 지점에서부터 도착 지점까지 이동하면서, 각 이동 시에 물이 도달하는 시간(depth)보다 먼저 도착할 수 있는지 검사한다.
• 이동 가능한 칸은 바위('X')가 없는 칸이며, 이동 횟수를 저장하는 2차원 배열(visited)을 사용한다.

• 만약 도착 지점에 도달할 수 있다면 그 때의 이동 횟수를, 도달할 수 없다면 "KAKTUS"를 출력한다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int r, c; cin >> r >> c;
    vector<vector<char>> board(r, vector<char>(c));
    vector<vector<int>> depth(r, vector<int>(c, INT_MAX));
    queue<pair<int, int>> bfs;
    pair<int, int> start, end;
    int offset[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };

    // 보드 입력 및 초기 상태 설정
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'S')
                start = { i, j };
            if (board[i][j] == 'D')
                end = { i, j };
            if (board[i][j] == '*') {
                bfs.push({ i, j });
                depth[i][j] = 0;
            }
        }
    }

    // 첫 번째 BFS: 물 확산 시뮬레이션
    while (!bfs.empty()) {
        int x, y; tie(y, x) = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + offset[i][0];
            int yy = y + offset[i][1];
            if (xx < 0 || xx >= c || yy < 0 || yy >= r) continue;
            if (board[yy][xx] == '.' && depth[yy][xx] > depth[y][x] + 1) {
                bfs.push({ yy, xx });
                depth[yy][xx] = depth[y][x] + 1;
            }
        }
    }

    // 두 번째 BFS: 탈출 경로 탐색
    vector<vector<int>> visited(r, vector<int>(c, INT_MAX));
    bfs.push(start);
    visited[start.first][start.second] = 0;
    while (!bfs.empty()) {
        int x, y; tie(y, x) = bfs.front();
        if (bfs.front() == end) {
            cout << visited[y][x];
            return 0;
        }
        bfs.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + offset[i][0];
            int yy = y + offset[i][1];
            if (xx < 0 || xx >= c || yy < 0 || yy >= r || board[yy][xx] == 'X')
                continue;
            // 물이 도착하는 시간보다 더 빠르게 이동할 수 있어야 한다.
            if (depth[yy][xx] > visited[y][x] + 1 && visited[yy][xx] > visited[y][x] + 1) {
                bfs.push({ yy, xx });
                visited[yy][xx] = visited[y][x] + 1;
            }
        }
    }

    cout << "KAKTUS";
}