[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨박꼭질4)

포인트

1. BFS (너비 우선 탐색) 

2. 이번 조건은 방문했던 경로들을 기억을 할 수 있는가 이다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

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

using namespace std;
const int MAX = 100001;

int parent[MAX]; //해당 지점 방문 직전 지점 저장
bool visited[MAX];
vector<int> map; //경로 저장

int n, m;

int bfs() {
    queue<pair<int, int>> q; // 페어 큐를 만든다.
    q.push({n, 0});
    visited[n] = 1;

    while (!q.empty()) { // 빌때 까지 반복
        int x, time;
        tie(x, time) = q.front();
        q.pop();

        if (x == m) //목적지 도달 조건
        {
            int index = x;
            while (index != n) { //처음까지 반복
                map.push_back(index); // 인덱스를 넣고
                index = parent[index]; // 가져와서 반복
            }
            map.push_back(n); // 처음 것 까지
            return time;
        }

        if (x + 1 < MAX && !visited[x + 1]) { //범위체크 && 방문하지 않았거나
            q.push(make_pair(x + 1, time + 1));
            visited[x + 1] = 1;
            parent[x + 1] = x;
        }

        if (x - 1 >= 0 && !visited[x - 1]) { //범위체크 && 방문하지 않았거나
            q.push(make_pair(x - 1, time + 1));
            visited[x - 1] = 1;
            parent[x - 1] = x;
        }

        if (x * 2 < MAX && !visited[x * 2]) { //범위체크 && 방문하지 않았거나
            q.push(make_pair(x * 2, time + 1));
            visited[x * 2] = 1;
            parent[x * 2] = x;
        }
    }
}


int main() {
    cin >> n >> m;
    cout << bfs() << endl;

    //거꾸로 저장되어있으므로
    for (int i = map.size() - 1; i >= 0; i--)
        cout << map[i] << ' ';

    cout << '\n';

    return 0;

}