[백준 13700] 완전 범죄 (C++)

문제링크 : https://www.acmicpc.net/problem/13700

13700번: 완전 범죄

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, S, D, F, B, K; //건물, 금은방, 집, 앞으로, 뒤로, 경찰서
int arr[100001]; //경찰서
int visited[100001]; //방문 여부
int cnt[100001]; //횟수 카운트
queue<int>q;

void BFS(int n)
{
    q.push(n);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if(cur == D) return;

        int next_front = cur + F; //앞으로
        int next_back = cur - B; //뒤로

        if(next_front <= N) //앞 범위 조건
        {
            if(!arr[next_front] && !visited[next_front])
            {
                visited[next_front] = 1;
                q.push(next_front);
                cnt[next_front] = cnt[cur] + 1;
            }
        }

        if(next_back > 0) //뒤 범위 조건
        {
            if(!arr[next_back] && !visited[next_back])
            {
                visited[next_back] = 1;
                q.push(next_back);
                cnt[next_back] = cnt[cur] + 1;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> S >> D >> F >> B >> K;
    for(int i=0; i<K; i++)
    {
        int exist;
        cin >> exist;
        arr[exist] = 1; //경찰서 존재 위치
    }

    cnt[D] = MAX;
    BFS(S);

    if(cnt[D]==MAX) cout << "BUG FOUND"; //집 도착 불가
    else cout << cnt[D];
    
    return 0;
}

BFS 문제이다.

움직일 수 있는 방향이 앞과 뒤 2방향인 것을 고려하면 된다.

처음에 경찰서의 존재 위치를 표시해주고, 경찰서도 아니고 아직 가보지도 않은 곳만 골라서 가면 된다.

그러면서 해당 위치에 따른 카운트 값을 누적해가면 된다.