[BOJ 1697] 숨바꼭질 C++

난이도: Silver 2
번호: 1697
생성일: March 4, 2023 7:53 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

1697번: 숨바꼭질

C++

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

int mini = 0xFFFFFFF;
int N, K;
bool visited[100001];

void BFS()
{
    queue<pair<int, int>> Q;
    Q.push({N, 0});
    visited[N] = true;

    while (!Q.empty())
    {
        int cur = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        if (cur == K)
        {
            mini = cnt;
            return;
        }

        if (cur * 2 <= K && !visited[cur * 2])
        {
            Q.push({cur * 2, cnt + 1});
            visited[cur * 2] = true;
        }

        if (cur + 1 <= K && !visited[cur + 1])
        {
            Q.push({cur + 1, cnt + 1});
            visited[cur + 1] = true;
        }

        if (cur - 1 >= 0 && !visited[cur - 1])
        {
            Q.push({cur - 1, cnt + 1});
            visited[cur - 1] = true;
        }
    }
}

int main()
{
    cin >> N >> K;

    BFS();

    if (mini == 0xFFFFFFF)
        cout << -1;
    else
        cout << mini;
}