[백준 1697번] [BFS] 숨바꼭질

처음에 단순히 3가지 케이스를 큐에다가 넣고 처리하려고 하였다.

 

하지만, 문제점이 데이터가 너무 많다.. 최악의 경우 3^100000인데 너무너무 크다.

 

이러한 문제점이 나타나는 근본적인 이유는 중복이 되기 때문이다.

 

잘 생각해보면 나중에 중복되는 숫자는 이전에 나온 것 보다 무조건 시간이 더 느릴 수 밖에 없으므로

기존에 방문한 것을 제외하고 처리해주면 된다.

 

일종의 DP 아이디어를 활용한다고 생각해도 무방하다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef pair<int, int> pii;

int main(void){
    fastio;
    int N, K;
    cin >> N >> K;
    queue<pii> data;
    int visited[2000001] = {0};
    data.push(make_pair(N, 0));

    if(N == K){
        cout << 0 << "\n";
        return 0;
    }

    while(true){
        pii check_value = data.front();
        data.pop();

        if(check_value.first + 1 == K || check_value.first - 1 == K || check_value.first * 2 == K){
            cout << check_value.second + 1 << "\n";
            return 0;
        }

        if(check_value.first * 2 <= 200000 && visited[check_value.first * 2] == 0){
            data.push(make_pair(check_value.first * 2, check_value.second + 1));
            visited[check_value.first * 2] = 1;
        } 
        if(check_value.first - 1 >= 0 && visited[check_value.first - 1] == 0){
            data.push(make_pair(check_value.first - 1, check_value.second + 1));
            visited[check_value.first - 1] = 1;

        }
        if(check_value.first + 1 <= 200000 && visited[check_value.first + 1] == 0){
            data.push(make_pair(check_value.first + 1, check_value.second + 1));
            visited[check_value.first + 1] = 1;
        }   
    }
}