1697 숨바꼭질

문제 링크

• 풀이

시작점에서 3가지 방향으로 BFS를 이용해 탐색하면 된다. 나는 BFS까지 이용한 것은 좋았는데 이미 지나친 지점의 중복 확인을 생각하지 않아 발생한 시간초과를 3가지 방향을 탐색하는 방법을 최적화 하려고 노력하였다. 그 결과 문제를 푸는데 너무 많은 시간을 할애하게 되었으며 스트레스를 받아 머리가 너무 아팠다.

중복을 확인하면 빠르게 잘 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

int N, K, chk[100001];

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

    cin >> N >> K;

    queue<pair<int, int>> q;

    q.push({ N, 0 });

    int t = 0, pos = 0;

    if (N == K)
        q.pop();

    while (!q.empty())
    {
        pos = q.front().first;
        t = q.front().second + 1;

        if (pos + 1 != K)
        {
            if ((pos + 1 < K) && !chk[pos + 1])
            {
                q.push({ pos + 1, t });
                chk[pos + 1] = 1;
            }
        }
        else
            break;

        if (pos - 1 != K)
        {
            if ((pos - 1 > 0) && !chk[pos - 1])
            {
                q.push({ pos - 1, t });
                chk[pos - 1] = 1;
            }
        }
        else
            break;

        if (pos * 2 != K)
        {
            if ((pos * 2 < 100001) && !chk[pos * 2])
            {
                q.push({ pos * 2, t });
                chk[pos * 2] = 1;
            }
        }
        else
            break;

        q.pop();
    }

    cout << t << "\n";

    return 0;
}