백준 1697번 숨바꼭질 (c++)

+1, -1, *2 로 탐색하는 경우에 대해서 BFS로 문제를 풀어주면 된다.

Queue에는 해당 위치와 몇번만에 도착했는지를 pair로 저장해서 넣어주고, 목적지에 도달했을 때, pair에 저장되어 있는 값을 확인해주면 된다.

#include <iostream>
#include <queue>

using namespace std;

bool visited[100010];

int main()
{
    for (int i = 0; i < 100010; i++)
    {
        visited[i] = false;
    }

    int n, k;
    cin >> n >> k;
    queue<pair<int, int>> q;
    pair<int, int> start = make_pair(n, 0);

    q.push(start);
    visited[n] = true;
    int answer = 0;
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();
        if (p.first == k)
        {
            answer = p.second;
            break;
        }
        if (p.first - 1 >= 0 && !visited[p.first - 1])
        {

            q.push(make_pair(p.first - 1, p.second + 1));
            visited[p.first - 1] = true;
        }
        if (p.first + 1 <= 100000 && !visited[p.first + 1])
        {
            q.push(make_pair(p.first + 1, p.second + 1));
            visited[p.first + 1] = true;
        }
        if (p.first * 2 <= 100000 && !visited[p.first * 2])
        {
            q.push(make_pair(p.first * 2, p.second + 1));
            visited[p.first * 2] = true;
        }
    }
    cout << answer << endl;
    return 0;
}