[BOJ 13549] 숨바꼭질 3 C++

난이도: Gold 5
번호: 13549
생성일: March 12, 2023 9:33 PM
알고리즘 분류: 0-1 너비 우선 탐색, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라
언어: C++

13549번: 숨바꼭질 3

C++

#include <cstdio>
#include <deque>

using namespace std;

int N, K;
int visit[100001];

int BFS()
{
    deque<int> dq;
    dq.push_back(N);
    visit[N] = 1;

    while (!dq.empty())
    {
        int cur = dq.front();
        dq.pop_front();

        if (cur == K)
            return visit[cur] - 1;

        if (cur * 2 < 100001 && !visit[cur * 2])
        {
            dq.push_front(cur * 2);
            visit[cur * 2] = visit[cur];
        }
        if (cur > 0 && !visit[cur - 1])
        {
            dq.push_back(cur - 1);
            visit[cur - 1] = visit[cur] + 1;
        }
        if (cur + 1 < 100001 && !visit[cur + 1])
        {
            dq.push_back(cur + 1);
            visit[cur + 1] = visit[cur] + 1;
        }
    }
    return -1;
}

int main(void)
{
    scanf("%d %d", &N, &K);
    printf("%d", BFS());
    return (0);
}