[BOJ] 백준 3055 탈출

출처: https://www.acmicpc.net/problem/3055

 Input 

3 6

D...*.

.X.X..

....S.

 

 Output 

6

물이 확장되는 BFS와 고슴도치가 이동하는 BFS 각각 구현

고슴도치가 물이 찰 예정인 곳을 이동할 수 없으므로

물에 대한 BFS를 먼저 수행한 후, 고슴도치 이동에 대한 BFS 수행.

---

#include <iostream>
#include <queue>
#define endl "\n"
#define MAX 50
using namespace std;
 
int R, C;
char map[MAX][MAX];
bool visited[MAX][MAX];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
pair<int, int> startPos, endPos;
queue<pair<int, int>> water;
 
 
void BFS(){
    // 두더지의 위치(x, y)와 경과시간
    queue<pair<pair<int, int>, int>> mole;
    mole.push(make_pair(make_pair(startPos.first, startPos.second), 0));
    visited[startPos.first][startPos.second] = true;
 
    // 물과 두더지 순으로 BFS 탐색
    while (!mole.empty()){
 
        // 먼저 물부터 확장
        int curWaterSize = water.size();
        for (int i = 0; i < curWaterSize; i++) {
            int curX = water.front().first;
            int curY = water.front().second;
            water.pop();
 
            for (int j = 0; j < 4; j++) {
                int nextX = curX + dx[j];
                int nextY = curY + dy[j];
 
                if (nextX < 0 || nextY < 0 || nextX >= R || nextY >= C) continue;
                // 빈칸인 경우만 물을 확장
                if (map[nextX][nextY] == '.') {
                    map[nextX][nextY] = '*';
                    water.push(make_pair(nextX, nextY));
                }
            }
        }
        
        // 현재 시간에서 가능한 두더지 이동
        int curMoleSize = mole.size();
        for (int i = 0; i < curMoleSize; i++) {
            int curX = mole.front().first.first;
            int curY = mole.front().first.second;
            int result = mole.front().second;
            mole.pop();
 
            // 목적지 도달 시
            if (curX == endPos.first && curY == endPos.second){
                cout << result << endl;
                return;
            }
 
            for (int j = 0; j < 4; j++){
                int nextX = curX + dx[j];
                int nextY = curY + dy[j];
                // 배열 범위를 벗어나는 경우
                if (nextX < 0 || nextY < 0 || nextX >= R || nextY >= C)
                    continue;
                // 이미 방문한 곳이거나 물 혹은 벽이 있는 경우
                if (visited[nextX][nextY] || map[nextX][nextY] == 'X' || map[nextX][nextY] == '*')
                    continue;
                
                visited[nextX][nextY] = true; // 방문표시
                mole.push(make_pair(make_pair(nextX, nextY), result + 1));
                
            }
        }
    }
    cout << "KAKTUS" << endl;
}
 
int main() {
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            // 두더지 위치(시작 위치)
            if (map[i][j] == 'S') startPos = make_pair(i, j);
            // 비버 굴(목적지)
            else if (map[i][j] == 'D') endPos = make_pair(i, j);
            // 물의 위치
            else if (map[i][j] == '*') water.push(make_pair(i, j));
            
        }
    }
 
    BFS();
}