백준 13549번 - 숨바꼭질 3 (C++)

해결 방법

BFS를 사용해 풀이.
다만 최적화를 진행해주지 않으면 1회전당 3배수씩 큐의 크기가 어마무시하게 늘어나기 때문에 매 위치마다의 최고기록을 저장해두고, 해당 기록보다 더 큰 시간이 들어오면 더이상 진행하지 못하는 식의 약간의 최적화를 추가하였다. (안하면 큐가 너무 커져서 메모리 초과남)

아쉬웠던 점

골드 5를 보고 너무 날먹하려는 생각에 최적화를 하나도 진행하지 않고 했다가 메모리 초과를 너무 많이 봤다...
사실 문제를 맞추는것보단 결국 더 높은 레벨 풀기 위해서는 효율적으로 푸는게 중요한데 스스로 반성합니다....

코드

#include <iostream>
#include <queue>
using namespace std;
 
int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K, Ans = 99999999;
    cin >> N >> K;
    vector<int> visit(100001, 99999999);
 
    queue<pair<int, int>> que;
    que.emplace(N, 0);
    while (!que.empty())
    {
        auto pair = que.front();
        int num = pair.first;
        int count = pair.second;
        que.pop();
 
        if (num == K)
        {
            if(Ans > count)
                Ans = count;
            continue;
        }
        if(Ans < count)
            continue;
        
        if(visit[num] > count)
            visit[num] = count;
        else
            continue;
 
        if(num > 0)
            que.emplace(num-1, count+1);
        if(num < 100000)
            que.emplace(num+1, count+1);
        if(num < K && num != 0 && num <= 50000)
            que.emplace(num*2, count);
    }
 
    cout << Ans;
    
    return 0;
}