BOJ 3055번 탈출

BOJ : https://www.acmicpc.net/problem/3055

github : https://github.com/junho0956/Algorithm/blob/master/3055/3055/%EC%86%8C%EC%8A%A4.cpp

 

고슴도치는 "물이 찰 예정이 아닌 곳" 으로 이동할 수 있습니다.

그러므로 물에 대한 BFS 를 먼저 탐색한 후에, 고슴도치가 갈 수 있는 곳으로 BFS 를 탐색해주시면 됩니다.

** 고슴도치가 있던 자리에는 물이 차도 상관없습니다. 고슴도치는 물이 찰 예정인 곳에서는 움직일 수 있습니다 **

 

#include <iostream>
#include <queue>
using namespace std;
 
typedef pair<pair<int,int>, int> pii;
int r, c;
char arr[50][50];
bool gvisit[50][50];
bool wvisit[50][50];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
queue<pii> gos;
queue<pii> water;
 
bool success = false;
int ans;
 
void escape() {
    int day = 0;
    while (!success) {
 
        while (!water.empty()) {
            int y = water.front().first.first;
            int x = water.front().first.second;
            int cnt = water.front().second;
            if (day != cnt) break;
            water.pop();
 
            if (wvisit[y][x]) continue;
            wvisit[y][x] = true;
 
            for (int i = 0; i < 4; i++) {
                int yy = y + my[i];
                int xx = x + mx[i];
                if (yy >= 0 && yy < r && xx >= 0 && xx < c) {
                    if (!wvisit[yy][xx] && arr[yy][xx] != 'D' && arr[yy][xx] != 'X') {
                        arr[yy][xx] = '*';
                        water.push({ {yy,xx},cnt + 1 });
                    }
                }
            }
        }
        
        bool move = false;
        while (!gos.empty()) {
            int y = gos.front().first.first;
            int x = gos.front().first.second;
            int cnt = gos.front().second;
            if (cnt != day) break;
            gos.pop();
 
            if (arr[y][x] == 'D') {
                success = true;
                ans = day;
                break;
            }
 
            if (gvisit[y][x]) continue;
            gvisit[y][x] = true;
 
            for (int i = 0; i < 4; i++) {
                int yy = y + my[i];
                int xx = x + mx[i];
                if (yy >= 0 && yy < r && xx >= 0 && xx < c) {
                    if (!gvisit[yy][xx] && arr[yy][xx] != '*' && arr[yy][xx] != 'X') {
                        gos.push({ {yy,xx},cnt+1 });
                        move = true;
                        if (arr[yy][xx] == '.') arr[yy][xx] = 'S';
                    }
                }
            }
        }
        if (!move) break;
        day++;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'S') gos.push({ {i,j},0 });
            if (arr[i][j] == '*') water.push({ {i,j},0 });
        }
    }
 
    escape();
 
    if (success) cout << ans;
    else cout << "KAKTUS";
 
    return 0;
}