백준 13700번 - 완전 범죄

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

BFS를 이용하여 이동 회수를 최소로 하는 문제로

이전에 게시한 1697번 숨바꼭질 문제와 거의 유사한 문제이다.

visited 배열을 이용하여 이전에 방문을 한적이 없을 때만 다음 좌표로 이동하도록 큐에 담았으며

경찰서의 위치를 -1로 표시하여 이동할 수 없도록 했다.

이동 회수가 적은 순서대로 큐에 담아지기 때문에

큐에 담긴 위치가 빈털털이의 집이라면 이동회수는 최소가 되어 바로 답을 출력하면 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    
    int ans=-1;
    int N,S,D,F,B,K;
    cin>>N>>S>>D>>F>>B>>K;
    
    int k;
    vector<int> visited(N+1,0);
    for(int i=0;i<K;i++){
        cin>>k;
        visited[k]=-1; //경찰서 위치
    }
    
    queue<pair<int,int>> q;
    q.push(make_pair(S,0));
    while(!q.empty()){
        int location=q.front().first;
        int cnt=q.front().second;
        q.pop();
        
        if(location==D){
            ans=cnt;
            break;
        }
        
        if(location+F<=N && visited[location+F]==0){
            visited[location+F]++;
            q.push(make_pair(location+F,cnt+1));
        }
        
        if(location-B>=1 && visited[location-B]==0){
            visited[location-B]++;
            q.push(make_pair(location-B,cnt+1));
        }
    }
    
    if(ans==-1) cout<<"BUG FOUND"<<endl;
    else    cout<<ans<<endl;
    
    return 0;
}