백준 3055번 [탈출](C++) -yes6686- 티스토리

백준 문제 풀이: 3055 (탈출)

---

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

문제 설명:

고슴도치가 물을 피해 비버의 굴로 탈출해야 하는 시뮬레이션 문제입니다. 지도에는 물(*), 돌(X), 비버의 굴(D), 고슴도치(S), 빈 공간(.)이 있으며, 매 시간마다 물은 인접한 칸으로 퍼지고, 고슴도치는 물이 퍼지기 전의 빈 칸 또는 굴로 이동할 수 있습니다. 고슴도치가 굴에 도달할 수 있는 최소 시간을 출력하거나, 불가능한 경우 "KAKTUS"를 출력합니다.

---

문제 해결 코드

// 3055번: 탈출
// 물 확산 BFS → 고슴도치 이동 BFS (물보다 먼저 도착해야 함)

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int arr[51][51];         // 고슴도치 이동 시간 기록
int w[51][51];           // 물 도착 시간 기록
int visited[51][51];     // 방문 여부
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int Dx, Dy;              // 비버의 굴 위치
int sx, sy;              // 고슴도치 시작 위치
int r, c;

int minAns = 251;

queue<pair<int, int>> q;
queue<pair<int, int>> ww;

void bfs(int x, int y, int k) {
    q.push({ x, y });
    visited[x][y] = 1;
    if (k == 1) w[x][y] = 0;

    while (!q.empty()) {
        int kx = q.front().first;
        int ky = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = kx + dx[i];
            int ny = ky + dy[i];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if (arr[nx][ny] == -1 || visited[nx][ny]) continue;
            visited[nx][ny] = 1;

            if (k == 1) { // 물
                if (Dx != nx || Dy != ny) { // 비버의 굴은 물이 차지 못함
                    if (w[nx][ny] == 0 || w[nx][ny] > w[kx][ky] + 1) {
                        w[nx][ny] = w[kx][ky] + 1;
                        q.push({ nx, ny });
                    }
                }
            } else { // 고슴도치
                if (Dx == nx && Dy == ny) {
                    minAns = min(minAns, arr[kx][ky] + 1);
                } else {
                    if (w[nx][ny] == 0 || arr[kx][ky] + 1 < w[nx][ny]) {
                        arr[nx][ny] = arr[kx][ky] + 1;
                        q.push({ nx, ny });
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            if (s[j] == 'S') {
                sx = i;
                sy = j;
            } else if (s[j] == 'D') {
                Dx = i;
                Dy = j;
            } else if (s[j] == '*') {
                ww.push({ i, j });
            } else if (s[j] == 'X') {
                arr[i][j] = -1;
            }
        }
    }

    // 물 확산 먼저 BFS
    while (!ww.empty()) {
        int kx = ww.front().first;
        int ky = ww.front().second;
        ww.pop();
        bfs(kx, ky, 1);
        memset(visited, 0, sizeof(visited));
    }

    // 고슴도치 이동 BFS
    bfs(sx, sy, 2);

    if (minAns == 251) {
        cout << "KAKTUS" << '\n';
    } else {
        cout << minAns << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 두 번의 BFS 수행 (물 확산 → 고슴도치 이동)
• 구현 흐름:
  • 1단계: 모든 물에 대해 BFS로 각 칸에 물이 도달하는 시간 기록
  • 2단계: 고슴도치 BFS 수행. 물보다 먼저 도달 가능한 칸만 이동
  • 도착 시 minAns 갱신
• 시간 복잡도: O(R ⋅ C)

---

결과

고슴도치가 비버의 굴에 도달 가능한 최소 시간을 출력합니다. 도달할 수 없다면 KAKTUS를 출력합니다.

예시 입력:
3 3
D.*
...
.S.

예시 출력:
3

다른 접근 방식이나 질문이 있다면 댓글로 공유해주세요!