[BaekJoon] 3055 탈출 :: monton

문제

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

풀이

가중치가 없고 최단 거리를 구하는 문제이므로 bfs 사용

일단 물이 들어가는 큐와 고슴도치의 위치를 담는 큐 이렇게 2개를 구성한 다음

큐에 물을 일단 담고 고슴도치 위치를 넣는다

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int R, C,ans,flag;
char arr[51][51];
int smap[51][51];
int wmap[51][51];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int main() {
    cin >> R >> C;
 
    queue <int> sx, sy, wx, wy;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'S') sx.push(i), sy.push(j), smap[i][j] = 1;
            if (arr[i][j] == '*') wx.push(i), wy.push(j), wmap[i][j] = 1;
        }
    }
 
    while (!sx.empty()) {
        
        int wcnt = wx.size();
        while (wcnt--) {
            int x = wx.front();
            int y = wy.front();
            wx.pop(), wy.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
 
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if (wmap[nx][ny]||arr[nx][ny]=='*'|| arr[nx][ny] == 'D' || arr[nx][ny] == 'X') continue;
                wx.push(nx), wy.push(ny);
                wmap[nx][ny] = 1;
            }
        }
 
        int scnt = sx.size();
        while (scnt--) {
            int x = sx.front();
            int y = sy.front();
            sx.pop(), sy.pop();
 
            if (arr[x][y] == 'D') {
                flag = 1;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
 
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if (smap[nx][ny] || wmap[nx][ny]||arr[nx][ny] == '*' || arr[nx][ny] == 'X') continue;
                sx.push(nx), sy.push(ny);
                smap[nx][ny] = 1;
            }
        }
        if (flag) break;
        ans++;
    }
    if (flag) cout << ans;
    else cout << "KAKTUS";
}

유사 문제

[BaekJoon] 5427 불 https://www.acmicpc.net/problem/5427