Softeer GINI야 도와줘 c++

문제 URL : https://softeer.ai/practice/6271

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제 접근법 : bfs를 두번사용하면 되는문제입니다.

소나기가 먼저퍼진후, 그다음 시작점에서 끝점까지 갈수있는지 확인하는 단순 bfs문제입니다.

처음 할때 실수로 시작점과 끝점을 바꿔서 코딩하다가 1시간넘게 안풀려서 의아했었는데

시작포인트와 끝포인트가 달라졌다는것을 깨닫고 풀렸네요

 

소스코드 : 

//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> board;
vector<pair<int,int>> rv;
int sy,sx,fy,fx;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
void input(){
    cin>>n>>m;
    char c;
    board = vector<vector<int>>(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j =0;j<m;j++){
            cin>>c;
            if(c=='H'){
                tie(fy,fx)={i,j};
            }
            else if(c=='W'){
                tie(sy,sx)={i,j};
            }
            else if(c=='*'){
                rv.push_back({i,j});
            }
            else if(c=='X'){
                board[i][j]=1;
            }
        }
    }
}
bool isrange(int y,int x){
    return 0<=y&&y<n&&0<=x&&x<m;
}

vector<vector<int>> bfs(vector<pair<int,int>> &v,vector<vector<int>> check,int rain){
    queue<tuple<int,int,int>> q;
    for(int i =0;i<v.size();i++){
        q.push({v[i].first,v[i].second,0});
        check[v[i].first][v[i].second]=0;
    }
    while(!q.empty()){
        int y,x,cnt;
        tie(y,x,cnt)=q.front();
        q.pop();
        for(int i =0;i<4;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(isrange(ny,nx)&&cnt+1<check[ny][nx]&&board[ny][nx]==0){
                if(rain){
                    if((ny==sy&&nx==sx) ||(ny==fy&&nx==fx))continue;
                    q.push({ny,nx,cnt+1});
                    check[ny][nx]=cnt+1;
                }
                else{
                    q.push({ny,nx,cnt+1});
                    check[ny][nx]=cnt+1;
                }
            }
        }
    }
    return check;
}
void solve(){
    vector<vector<int>> check(n,vector<int>(m,1e8));
    vector<vector<int>> check2 = bfs(rv,check,1);
    vector<pair<int,int>> p={{sy,sx}};
    vector<vector<int>> res = bfs(p,check2,0);

    if(check2[fy][fx]==res[fy][fx]){
        cout<<"FAIL"<<"\n";
    }
    else{
        cout<<res[fy][fx]<<"\n";
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();



}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.