[백준 12851번] 숨바꼭질2

문제 링크: https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

<문제 풀이> BFS
https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

1697번 문제와 비슷한데

1697번 문제에서는 큐에 push를 할 때 방문 체크를 해줬는데 이문제에서는 큐에서 pop 할 때 방문 체크를 해야 합니다.

왜냐하면 push를 할 때 방문 체크를 해버리면 같은 레벨에서 n=k을 만족하는 정점을 다시 넣을 수 없기 때문입니다.

 

1. 큐에서 pop 할 때 방문 체크

2. n=k을 만족하는 정점의 level 보다 더 큰 level을 가진 정점을 만나면 종료

3. n=k을 만족하는 정점을 최초로 찾았을 때 level 저장

->두 번째 부터는 개수만 카운트

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int n, k; 
int visited[100001];
int res = 0;
int level = -1;
void bfs() {
    queue<pair<int, int> >Q;
    Q.push({n, 0});
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        visited[cur.X] = true;
        if (level != -1 && cur.Y > level) return;
 
        if (level == -1 && cur.X == k) { //최초 발견
            level = cur.Y;
            res++;
        }
        else if (level != -1 && cur.X == k) {//2회 이상 발견
            res++;
        }
        if (2 * cur.X <= 100000 && !visited[2 * cur.X]) {
            Q.push({ 2 * cur.X, cur.Y + 1});
        }
        if (cur.X - 1 >= 0 && !visited[cur.X - 1]) {
            Q.push({cur.X - 1, cur.Y + 1 });
 
        }
        if (cur.X + 1 <= 100000 && !visited[cur.X + 1]) {
            Q.push({cur.X + 1, cur.Y + 1 });
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> k;
 
    bfs();
    cout << level <<'\n';
    cout << res;
    return 0;
}