[백준 3055번] 탈출

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

3055번: 탈출

<문제 풀이> BFS, 최단거리
이문제는 모든 물에 대해서(물을 모두 큐에 담으면 됨) BFS로 물에서 모든 정점까지의 최단 거리를 구하고, 고슴 도치에 대해서 똑같이 BFS를 진행하면서 물 보다 더 최단 거리로 이동할 수 있는 경우만 큐에 담으면 됩니다.

 

주의할 점은 입력으로 물이 없을 수도 있습니다(물이 없으면 물의 visited 최단 거리 배열 값은 -1).

 

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
 
#define X first
#define Y second
 
int R, C;
char board[50][50];
int visitedW[50][50];
int visitedS[50][50];
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
void wBFS() {
    queue<pair<int, int> > Q;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == '*') {
                Q.push({ i, j });
                visitedW[i][j] = 0;
            }
            }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;
            if (board[nx][ny] == 'D' || board[nx][ny] == 'X') continue;
            if (visitedW[nx][ny] != -1)continue;
            Q.push({ nx, ny });
            visitedW[nx][ny] = visitedW[cur.X][cur.Y] + 1;
        }
    }
}
 
int sBFS() {
    int ret = -1;
    queue<pair<int, int> > Q;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'S') {
                Q.push({ i, j });
                visitedS[i][j] = 0;
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;
            if (board[nx][ny] == 'X') continue;
            if (visitedS[nx][ny] != -1)continue;
            if (board[nx][ny] != 'D' && visitedW[nx][ny] != -1 && visitedS[cur.X][cur.Y] + 1 >= visitedW[nx][ny])continue; //물 보다 늦게 도착하면 무시
            Q.push({ nx, ny });
            visitedS[nx][ny] = visitedS[cur.X][cur.Y] + 1;
            if (board[nx][ny] == 'D') {
                return visitedS[nx][ny];
            }
        }
    }
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
        }
    }
    fill(&visitedW[0][0], &visitedW[49][50], -1);
    fill(&visitedS[0][0], &visitedS[49][50], -1);
    wBFS();
    int res = sBFS();
    if (res == -1) cout << "KAKTUS";
    else cout << res;
    return 0;
}