백준 13549번 : 숨바꼭질 3

• Solved.ac 기준 : 골드 5
• 사용언어 C++

• BFS를 이용해 이동 가능한 모든 경우를 탐색
• 순간이동은 시간이 0임을 인지

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int findTime(int n, int k) {
    if (n >= k) {
        return n - k;
    }

    vector<int> visited(100001, -1);
    queue<int> que;

    que.push(n);
    visited[n] = 0;

    while (!que.empty()) {
        int current = que.front();
        que.pop();

        if (current == k) {
            return visited[current];
        }

        if (current * 2 <= 100000 && visited[current * 2] == -1) {
            que.push(current * 2);
            visited[current * 2] = visited[current];
        }

        // 걷는 것은 시간이 1초 증가
        if (current - 1 >= 0 && visited[current - 1] == -1) {
            que.push(current - 1);
            visited[current - 1] = visited[current] + 1;
        }

        if (current + 1 <= 100000 && visited[current + 1] == -1) {
            que.push(current + 1);
            visited[current + 1] = visited[current] + 1;
        }
    }

    return -1;
}

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

    int n, k;
    cin >> n >> k;

    cout << findTime(n, k);

    return 0;
}