숨바꼭질 2 (feat. 백준, 12851번)

숨바꼭질 2
https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
pair<int, int> arr[100001];         // N으로부터 총 횟수, 방법
void bfs(register int n, register int k){
    queue<pair<int, int>> q;        // 위치, 위치까지 온 누적 횟수
    q.push(make_pair(n, 0));
    if(n == k){
        ++arr[n].second;
        return;
    }
    while(!q.empty()){
        auto v = q.front(); q.pop();
        auto pos = v.first, cnt = v.second;
        if(pos - 1 >= 0){
            if(cnt + 1 == arr[pos - 1].first)
                q.push(make_pair(pos - 1, cnt + 1)), ++arr[pos - 1].second;
            else if((arr[pos - 1].first == 0 && arr[pos - 1].second == 0) || cnt + 1 < arr[pos - 1].first)
                q.push(make_pair(pos - 1, cnt + 1)), arr[pos - 1].first = cnt + 1, arr[pos - 1].second = 1;
        }
        if(pos + 1 <= 100000){
            if(cnt + 1 == arr[pos + 1].first)
                q.push(make_pair(pos + 1, cnt + 1)), ++arr[pos + 1].second;
            else if((arr[pos + 1].first == 0 && arr[pos + 1].second == 0) || cnt + 1 < arr[pos + 1].first)
                q.push(make_pair(pos + 1, cnt + 1)), arr[pos + 1].first = cnt + 1, arr[pos + 1].second = 1;
        }
        if(0 < pos && (pos << 1) <= 100000){
            if(cnt + 1 == arr[pos << 1].first)
                q.push(make_pair(pos << 1, cnt + 1)), ++arr[pos << 1].second;
            else if((arr[pos << 1].first == 0 && arr[pos << 1].second == 0) || cnt + 1 < arr[pos << 1].first)
                q.push(make_pair(pos << 1, cnt + 1)), arr[pos << 1].first = cnt + 1, arr[pos << 1].second = 1;
        }
    }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, K;
    cin >> N >> K;
    bfs(N, K);
    cout << arr[K].first << "\n" << arr[K].second;
    return 0;
}
// *&)*@*

 

반응형

1. 문제의 조건과 같이 N 자리에서 -1, +1, *2 의 경우에 대해서 걸린 시간과 이동 가능한 횟수를 기록합니다.
2. 단, N == K인 경우, 걸린 시간은 0초이고 이동 가능한 횟수는 N == K 밖에 없으므로 0 1 을 출력해야 합니다.