BOJ 13913번 숨바꼭질4

BOJ : https://www.acmicpc.net/problem/13913

github : https://github.com/junho0956/Algorithm/blob/master/13913/13913/%EC%86%8C%EC%8A%A4.cpp

 

BFS 의 특성상

처음 방문한 곳은 다시 방문할 필요가 없어진다.

이를 이용한다면

방문배열뿐만 아니라 이 정점(숫자)을 방문하기 직전의 정점을 기억할 배열을 따로 만들어둔다면

이 배열 역시 단 한번만 방문하면 되기 때문에 이 정점을 방문하기 직전의 정점만 저장해두면 

쉽게 문제를 해결할 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
 
int N, K;
int btk[100001];
queue<pair<int, int> > q;
bool visit[100001];
 
int main() {
    cin >> N >> K;
 
    for (int i = 0; i <= 100000; i++) btk[i] = -1;
 
    int Min = 999999;
    btk[N] = N;
 
    q.push({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > 100000 || now < 0) continue;
 
        if (visit[now]) continue;
        visit[now] = true;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            break;
        }
 
        if (now != 0 && now < K && now * 2 <= 100000) {
            q.push({ now * 2, cnt + 1 });
            if (btk[now * 2] == -1) btk[now * 2] = now;
        }
        if (now - 1 >= 0) {
            q.push({ now - 1,cnt + 1 });
            if (btk[now - 1] == -1) btk[now - 1] = now;
        }
        if (now + 1 <= 100000) {
            q.push({ now + 1,cnt + 1 });
            if (btk[now + 1] == -1) btk[now + 1] = now;
        }
    }
 
    stack<int> s;
    int back_check = K;
    s.push(K);
    while (1) {
        if (btk[back_check] != back_check) {
            s.push(btk[back_check]);
            back_check = btk[back_check];
        }
        else break;
    }
 
    cout << Min << endl;
    while (!s.empty()) {
        int num = s.top();
        s.pop();
        cout << num << ' ';
    }
 
    return 0;
}