BFS를 활용한 최단 거리 계산 in C++

현재 위치와 도착 위치를 알고있고, 앞뒤로 1칸 앞으로 5칸 움직일 수 있을때, 몇번을 움직여야 하는지 최단거리를 구하는 코드(1번 정점에서 출발)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int d[] = {1, -1, 5};
int s, e;
int dis[10001];
queue<int> Q;

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> s >> e;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        if (x == e) {
            cout << dis[x];
            return 0;
        }
        for (int i = 0; i < 3; i++) {
            int pos = x + d[i];
//          cout << "pos is : " << pos;
//          cout << '\n';
            if(pos < 0 || pos > 10000) continue;
            else if (dis[pos] == 0) {
                dis[pos] = dis[x] + 1;
                Q.push(pos);
            }
        }
    }
    return 0;
}

BFS활용 시, 먼저 나온 결과값이 최소 도달 거리이다. 따라서 따로 relaxing 해 줄 필요가 없다.

• dis[x] : 위치x에 있을때, 몇번 움직였는지 기록

ex)
5 14