Baekjoon 12851번 숨바꼭질 2

문제

https://www.acmicpc.net/problem/12851

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    // bfs
    queue<int> q;
    vector<int> visited(100001, 0);
    q.push(n);
    int way = 0;
    int time = -1;
    while(!q.empty()){
        time++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int x = q.front();
            q.pop();
            if(x == k) way++;
            visited[x] = 1;
            if(x-1 >= 0 && !visited[x-1]) q.push(x-1);
            if(x+1 <= 100000 && !visited[x+1]) q.push(x+1);
            if(x*2 <= 100000 && !visited[x*2]) q.push(x*2);
        }
        if(way) break;
    }
    cout << time << "\n" << way;
    return 0;
}

1697번 숨바꼭질에서 최단 시간의 방법의 개수를 추가로 묻는 bfs 문제이다.

방문 처리를 어느 시점에서 하느냐가 중요했는데, 정답이 될 수 있는 모든 방법의 개수를 구해야하므로 queue 에 같은 지점이 이미 있더라도 추가할 수 있게끔 구현해야한다.