[BOJ_C++] 1697번 : 숨박꼭질

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
bool visited[100001];
queue<pair<int, int>> q;

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

    int n, k, pos, depth; cin >> n >> k;


    q.push(pair<int, int>(n, 0));

    while (!q.empty()) {
        pos = q.front().first;
        depth = q.front().second;
        q.pop();

        if (pos == k) break;

        visited[pos] = true;

        if (pos - 1 >= 0 && !visited[pos - 1])
            q.push(pair<int, int>(pos - 1, depth + 1));
        if (pos + 1 <= 100000 && !visited[pos + 1])
            q.push(pair<int, int>(pos + 1, depth + 1));
        if (pos * 2 <= 100000 && !visited[pos * 2])
            q.push(pair<int, int>(pos * 2, depth + 1));
    }

    cout << depth;

    return 0;
}

• bfs를 이용하여 각 경우의 수에 대한 결과를 모두 계산한 후 pos와 k가 동일해질 경우 해당 depth를 출력한다.
• 다시말하자면 수빈이가 걷거나(x + 1 or x - 1), 순간이동하는 경우(2 * x)를 모두 계산하고 해당 노드로 이동하여 그에대한 경우를 또 계산한다.
• 이때 pos(x)와 k가 같아지면 해당 depth가 소요된 시간이므로 while문을 탈출하고 depth를 출력한다.

결과