[백준/C++] 3055번 탈출

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

3055번: 탈출

bfs문제다. 근데 주의할 점은 물 -> 고슴도치 -> 물 -> 고슴도치 순으로 bfs를 진행해줘야 한다는 것!

​

먼저 물을 담고 있는 큐의 사이즈만큼 탐색을 진행한다. 그리고 고슴도치 위치를 담고 있는 큐의 사이즈만큼 탐색을 진행해주면 된다.

생각보다 간단한데, 이런 유형의 문제를 처음 푸는 분들은 조금 당황할 수도 있다. 왜냐??

바로 큐의 사이즈만큼 탐색을 하기 때문이다. bfs문제에서 큐의 사이즈만큼 탐색은 곧 한 턴씩 탐색을 진행한다는 뜻이다!!

고민해보자. 큐의 사이즈가 아니라 기존 bfs처럼 큐가 빌 때 까지 물과 고슴도치에 대해 번갈아가며 탐색을 하게 되면, 한 턴에 한 번 증식하는 것이 아니라, 턴과 무관하게 증식한다..!​ 문제의 예시처럼 행렬이 크지 않은 경우 무의미할 수 있지만, 행렬이 커질수록 그 차이가 엄청나게 벌어진다!

#include <bits/stdc++.h>

using namespace std;

int r,c,sx,sy;
string s;
char board[51][51];
int dx[] ={-1,0,1,0};
int dy[] = {0,1,0,-1};

queue<pair<int,int>> water;
bool flood[51][51];
bool visited[51][51];
int dist[51][51];

void bfs_water(){
    int siz = water.size();
    while(siz--){
        int x = water.front().first;
        int y = water.front().second;
        water.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx <0 || nx >= r || ny < 0 ||ny >= c) continue;
            if(board[nx][ny]=='D' || board[nx][ny] == 'X' || flood[nx][ny]) continue;
            water.push({nx,ny});
            board[nx][ny] = '*';
            flood[nx][ny] = true;
        }
    }
}

void bfs(){
    queue<pair<int,int>> q;
    q.push({sx,sy});
    visited[sx][sy]=true;

    while(!q.empty()){
        bfs_water();
        int siz = q.size();
        while(siz--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if (board[x][y] == 'D') {
                cout << dist[x][y];
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (visited[nx][ny] || board[nx][ny] == '*' || board[nx][ny] == 'X') continue;

                q.push({nx, ny});
                visited[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
    }
    cout << "KAKTUS";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> r >> c;

    for(int i=0; i<r; i++){
        cin >> s;
        for(int j=0; j<s.size();j++){
            board[i][j]=s[j];
            if(board[i][j]=='S'){
                sx = i;
                sy = j;
            }
            else if(board[i][j]=='*'){
                water.push({i,j});
                flood[i][j]=true;
            }
        }
    }
    bfs();
}
​