[백준 12851번] [BFS] 숨바꼭질 2

이 문제와 숨바꼭질1과의 차이점은

중복되는 것의 유무를 어떻게 처리할 것인가에 대한 유무이다.

 

앞 문제에서는 queue에 넣을 때 visited를 처리하였다.

왜냐하면 어차피 동일한 시간이 걸리는 것이 존재해도 어차피 시간이 같으므로 지워도 무방하기 때문이다.

 

다만, 이 문제의 경우 최소일 때 몇 가지 인지 체크해야하는 문제이므로

동일한 시간이 걸리는 경우에는 모두 다 살려주어야 한다.

즉, visited처리하는 순간이 그 이후 타이밍이어야 한다.

 

즉, pop시키는 순간에 visited처리해 주면 1번과 근본적으로 동일하게 접근할 수 있다.

#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[100001] = {0};
    visited[N] = 1;
    data.push(make_pair(N, 0));

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

    int min_time = 987654321;
    int count_value = 0;

    while(data.size() != 0){
        pii check_value = data.front();
        data.pop();
        visited[check_value.first] = 1;

        if(check_value.second + 1 > min_time){
            cout << min_time << "\n";
            cout << count_value << "\n";

            return 0;
        }

        if(check_value.first + 1 == K || check_value.first - 1 == K || check_value.first * 2 == K){
            min_time = check_value.second + 1;
            if(check_value.first + 1 == K) count_value += 1;
            if(check_value.first - 1 == K) count_value += 1;
            if(check_value.first * 2 == K) count_value += 1;
            continue;
        }

        if(check_value.first * 2 <= 100000 && visited[check_value.first * 2] == 0){
            data.push(make_pair(check_value.first * 2, check_value.second + 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));

        }
        if(check_value.first + 1 <= 100000 && visited[check_value.first + 1] == 0){
            data.push(make_pair(check_value.first + 1, check_value.second + 1));
        } 
    }
    cout << min_time << "\n";
    cout << count_value << "\n";

    return 0;
}