[C++/알고리즘] 송아지 찾기(BFS:상태트리탐색)

1. 현재위치 s와 송아지의 위치 e가 주어진다.
2. 직선의 좌표 점은 1부터 10,000까지 이다.
3. 한 번의 이동시 현 좌표에서 1, -1, 5만큼 이동할 수 있다.

현재위치에서 최소 몇 번의 이동으로 송아지의 위치까지 가는가?

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

using namespace std;

int main(){
    int s, e, x;
    int pos[3] = {-1, 1, 5}, ch[10001];
    queue<int> Q;

    cin >> s >> e;
	
    // s부터 출발하기 때문, Q에 s를 넣는다.
    Q.push(s);
    // s에서 출발 - 이동 횟수 1회 더함
    ch[s] = 1;

    while(!Q.empty()){
        x = Q.front();
        Q.pop();
		
        // 현재위치에서 1, -1, 5만큼 이동한 것을 모두 체크한다.
        for(int i=0; i<3; i++){
            if(x+pos[i] < 0 || x+pos[i] > 10000) continue;
            
            if(ch[x+pos[i]] == 0){
                ch[x+pos[i]] += ch[x] + 1;
                Q.push(x+pos[i]);
                }
                
            // x에서 pos[i]만큼 이동한 좌표가 e라면 이동한 횟수 출력
            // 출발할때 이미 1을 더한 상태로 시작했기 때문에 이전좌표까지의 이동횟수를 출력한다.
            if(x+pos[i] == e){
                cout << ch[x];
                exit(0);
            }
        }
    }

    return 0;
}