[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질2)

포인트

1. BFS (너비 우선 탐색) 를 이해를 하고 있는가?

2. 숨바꼭질 2에서 중요한 점은 가장 빠른 경우의 수를 세는 것이다.  기존 BFS () 는 최초 도착 만을 세기 때문에 다른 방식으로 처리를 해주어야 한다. 

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;
#define MAX  100000 + 1

int cnt;
int time;
bool visited[MAX];
int n, m;

int second() {
    queue<pair<int, int>> q;
    q.push(make_pair(n, 0));
    visited[n] = 1;

    while (!q.empty()) {
        int x, xtime;
        tie(x, xtime) = q.front();
        q.pop();
        visited[x] = 1;

        //이미 목적지에 한번 도달했을 경우 cnt++
        if (time != 0 && time == xtime && x == m)
            cnt += 1;
        //최초로 목적지 도달시 최소 시간 기록하고 cnt++

        if (!time && x == m) {  // 목적지 도달
            time = xtime;
            cnt += 1;
        }

        //세 가지 경우의 수
        if (x + 1 < MAX && !visited[x + 1]) //범위체크 && 방문하지않거나 
            q.push(make_pair(x + 1, xtime + 1));

        if (x - 1 >= 0 && !visited[x - 1]) //범위체크 && 방문하지않거나 
            q.push(make_pair(x - 1, xtime + 1));

        if (x * 2 < MAX && !visited[x * 2]) //범위체크 && 방문하지않거나 
            q.push(make_pair(x * 2, xtime + 1));
    }
    return time;
}


int main() {

    cin >> n >> m;
    cout << second() << '\n';
    cout << cnt << '\n';

    return 0;
}