백준 16954

이번 문제도 bfs를 이용해서 풀었다.

먼저 짚고 넘어가야 할 점은

bfs가 시작될 지점이 하나가 아닌 다수라는 것.

즉, 물의 좌표와 고슴도치의 좌표 각각이 bfs를 시작해야한다는 것이다.

그럼 코드를 보겠다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class pos{
public:
    int x, y, min;
    pos(int a, int b, int c){
        x = a;
        y = b;
        min = c;
    }
    pos(){x = 0; y = 0; min = 0;}
};

char a[50][50];
bool check[50][50];
int dx[4] = {-1, 1, 0 ,0};
int dy[4] = {0, 0, -1, 1};
int r, c;
vector<pos> water;
pos start;
pos dest;

bool isIn(pos p){
    if(p.x < 0 || p.y < 0 || p.x >= r || p.y >= c) return false;
    return true;
}

int bfs(){
    queue<pos> q;
    queue<pos> w;
    for(pos p: water){
        w.push(p);
    }
    q.push(start);
    check[start.x][start.y] = true;
    int now = start.min;
    while(!q.empty()){
        pos node = q.front(); q.pop();
        if(now != node.min){
            now = node.min;
            int wSize = w.size();
            for(int i = 0; i < wSize; i++){
                pos pw = w.front(); w.pop();
                for(int j = 0; j < 4; j++){
                    pos nw = pos(pw.x+dx[j], pw.y+dy[j], pw.min+1);
                    if(isIn(nw) && a[nw.x][nw.y] == '.'){
                        a[nw.x][nw.y] = '*';
                        w.push(nw);
                    }
                }
            }
        }
        if(node.x == dest.x && node.y == dest.y) return node.min;
        else if(a[node.x][node.y] == '*') continue;
        for(int i = 0; i < 4; i++){
            pos next = pos(node.x+dx[i], node.y+dy[i], node.min+1);
            if(isIn(next) && (a[next.x][next.y] == '.' || a[next.x][next.y] == 'D') && check[next.x][next.y] == false){
                q.push(next);
                check[next.x][next.y] = true;
            }
        }
        
    }
    return -1;
}

int main(){
    cin >> r >> c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> a[i][j];
            if(a[i][j] == 'D') dest = pos(i, j, 0);
            else if(a[i][j] == 'S') start = pos(i, j, 0);
            else if(a[i][j] == '*') water.push_back(pos(i, j, 0));
        }
    }

    int result = bfs();
    if(result == -1) cout << "KAKTUS";
    else cout << result;
}

물의 첫 좌표들을 받아줄 water 벡터를 선언했고,(이건 후에 생각해보니 queue를 전역으로 선언했어도 됐겠다 싶었다.

S와 D 좌표를 각각 저장할 start, dest pos 객체를 생성했다.

다른 것보다 bfs 함수부를 보면 w 큐와 q 큐로 각각 bfs를 실행하는 것 볼 수 있다.

하지만 여기에 따른 차이는 q 큐로 인한 bfs는 우리가 지금껏 흔히 써온 bfs와 같은 방식으로 진행되는데, w 큐로 인한 bfs는 q 큐에 저장된 pos 객체의 min 값이 이전 pos 객체의 min 값이 변경됐을 때 진행된다.

즉, 문제의 말에 따르자면 고슴도치가 한칸 bfs를 진행한 후 홍수의 bfs가 한칸씩 진행된다고 볼 수 있다.

그렇게 어려운 문제는 아니지만 한번에 여러개의 bfs가 진행된 상황을 풀어내는 게 처음에는 힘들 수 있다고 생각한다.

그리고 이전에 풀었던 백준 16954 문제와 유사하긴 하지만, 16954 문제의 경우는 벽이 단순하게 위에서 아래로 한칸씩 이동한 것에 비해 이 문제는 bfs를 통해 물이 한칸씩 퍼져나간다는 것이 차이로, 조금 더 난이도 있는 문제가 아닌가 생각한다.