[Softeer/소프티어][level3] GINI야 도와줘 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=583&sw_prbl_sbms_sn=17050

Softeer

 

[난이도] level3
[유형] BFS

[풀이]
태범이와 소나기 모두 시간에 따라 1칸씩 움직이기 때문에 태범이의 다음 전진 가능한 위치를 저장하는 q1,
소나기의 위치를 저장하는 q2 두개의 queue를 선언한 뒤 BFS를 돌려주었습니다.
소나기부터 전진시킨 뒤 태범이를 전진시키야 소나기에 의해 범준이의 전진이 막히는지 정확히 파악할 수 있습니다.

 

 

#include <cstdio>
#include <queue>
using namespace std;
int R,C,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},ey,ex;
char map[50][50];
bool visit1[50][50],visit2[50][50];
int main(){
    scanf("%d%d",&R,&C);
    queue<pair<int,int>> q1,q2;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='W') {
                visit1[i][j]=1;
                q1.push({i,j});
            }
            else if(map[i][j]=='H') ey=i,ex=j;
            else if(map[i][j]=='*') {
                visit2[i][j]=1;
                q2.push({i,j});
            }
        }
    }
    int ans=0;
    while(!q1.empty()){
        int sz = q2.size();
        while(sz--){
            auto [cy,cx] = q2.front(); q2.pop();  
            for(int k=0;k<4;k++){
                int ny=cy+dy[k],nx=cx+dx[k];
                if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='X'||map[ny][nx]=='H'||visit2[ny][nx]) continue;
                visit2[ny][nx]=1;
                q2.push({ny,nx});
            }
        }
        sz = q1.size();
        while(sz--){
            auto [cy,cx] = q1.front(); q1.pop();  
            if(cy==ey&&cx==ex){
                printf("%d",ans);
                return 0;
            }
            for(int k=0;k<4;k++){
                int ny=cy+dy[k],nx=cx+dx[k];
                if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='X'||visit1[ny][nx]||visit2[ny][nx]) continue;
                visit1[ny][nx]=1;
                q1.push({ny,nx});
            }
        }
        ans++;
    }
    puts("FAIL");
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/GINI야_도와줘.cpp