13549 숨바꼭질

문제 링크

• 내 풀이

우선순위 큐를 이용한 풀이

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N, K;

int m[100001];

struct ele {
    int pos, t;
};

struct cmp {
    bool operator()(ele a, ele b)
    {
        return a.t > b.t;
    }
};

int solve()
{
    priority_queue<ele, vector<ele>, cmp> q;
    q.push({ N, 0 });

    for (int& z : m)
        z = 100001;
    m[N] = 0;

    while (!q.empty())
    {
        ele cur = q.top();
        q.pop();
        if (cur.pos == K)
        {
            return cur.t;
        }

        if (cur.pos * 2 <= 100000 && m[cur.pos * 2] > cur.t )
        {
            q.push({ cur.pos * 2, cur.t });
        }
        
        if (cur.pos + 1 <= 100000 && m[cur.pos + 1] > cur.t + 1)
        {
            m[cur.pos + 1] = cur.t + 1;
            q.push({ cur.pos + 1, cur.t + 1 });
        }
        if (cur.pos - 1 >= 0 && m[cur.pos - 1] > cur.t + 1)
        {
            m[cur.pos - 1] = cur.t + 1;
            q.push({ cur.pos - 1, cur.t + 1 });
        }
    }
    return -1;
}

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

    cin >> N >> K;

    int ret = solve();
    cout << ret << "\n";
    

    return 0;
}

0-1 BFS란?

0-1 BFS를 이용한 풀이

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N, K;

int m[100001];

int solve()
{
    deque<int> q;
    q.push_front(N);

    for (int& z : m)
        z = 100001;
    m[N] = 0;

    while (!q.empty())
    {
        int cur = q.front();
        int t = m[cur];
        q.pop_front();
        if (cur == K)
        {
            return t;
        }

        if (cur + 1 <= 100000 && m[cur + 1] > t + 1)
        {
            m[cur + 1] = t + 1;
            q.push_back(cur + 1);
        }
        if (cur - 1 >= 0 && m[cur - 1] > t + 1)
        {
            m[cur - 1] = t + 1;
            q.push_back(cur - 1);
        }

        while (cur && cur * 2 <= 100000)
        {
            if (m[cur * 2] > t)
            {
                m[cur * 2] = t;
                q.push_front(cur * 2);
            }
            cur *= 2;
        }
    }
    return -1;
}

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

    cin >> N >> K;

    int ret = solve();
    cout << ret << "\n";

    return 0;
}