백준 : 3055

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

3055번: 탈출

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
 
using namespace std;
 
int R,C;
char mymap[50][50];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
 
struct con
{
    int y;
    int x;
    int cnt;
};
 
 
void W_BFS(int y,int x,int cnt,queue <con>& Q_w){
    if(y>=R||y<0||x>=C||x<0) return;
 
    if(mymap[y][x] =='S'|| mymap[y][x]=='.') {
        mymap[y][x] = '*';
        Q_w.push({y,x,cnt+1});
    }
}
 
bool S_BFS(int y,int x,int cnt,queue <con>& Q_s){
    if(y>=R||y<0||x>=C||x<0) return false;
 
    if(mymap[y][x] == 'D'){
        return true;
    }
 
    if(mymap[y][x] == '.'){
        mymap[y][x] = 'S';
        Q_s.push({y,x,cnt+1});
        return false;
    }
    return false;
}
 
int main(void){
 
    cin>>R>>C;
 
    queue <con> Q_s;
    queue <con> Q_w;
 
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin>>mymap[i][j];
            if(mymap[i][j] == 'S'){
                Q_s.push({i,j,0});
            }else if(mymap[i][j] == '*'){
                Q_w.push({i,j,0});
            }
        }
    }
 
    con tmp_s;
    con tmp_w;
    int cnt=0;
    bool check= false;
 
    while(true){
 
        int ny,nx;
 
        while(true){
            if(Q_w.empty()) break;
            else if(cnt == Q_w.front().cnt){
                tmp_w = Q_w.front();
                Q_w.pop();
                for(int i=0;i<4;i++){
                    ny = dy[i] + tmp_w.y;
                    nx = dx[i] + tmp_w.x;
                    W_BFS(ny,nx,cnt,Q_w);
                }
            }else break;
        }
 
        while(true){
            if(Q_s.empty()){
                cout<<"KAKTUS";
                check = true;
                break;
            }
            else if(cnt == Q_s.front().cnt){
                tmp_s = Q_s.front();
                Q_s.pop();
                for(int i=0;i<4;i++){
                    ny = dy[i] + tmp_s.y;
                    nx = dx[i] + tmp_s.x;
 
                    if(S_BFS(ny,nx,cnt,Q_s)){
                        cout<<cnt+1;
                        check = true;
                        break;
                    }
                }                      
            }else break;
 
            if(check) break;
  
        }
        ++cnt;
        if(check) break;
    }
 
}