BOJ 12851번: 숨바꼭질 2

문제

문제 바로가기> BOJ 12851번: 숨바꼭질 2

12851번: 숨바꼭질 2

 

풀이

동생을 찾는 가장 빠른 시간이므로 bfs를 이용하였고,

가중치가 같지 않은 경우(걸음과 순간이동은 시간 당 이동할 수 있는 칸 수가 다름)에 속하므로 더 빠르게 찾을 수 있는 경우 큐에 다시 한번 넣어 주었다.

#include<iostream>
#include<queue>
#define MAX 100001
using namespace std;

int N, K;
int cost[MAX];

void input(){
    cin >> N >> K;
}

void solve(){

    // 1. 초기화
    int cnt = 1; // 방법 개수
    for (int i = 0; i < MAX; i++) cost[i] = MAX; // 가장 빠르게 찾을 수 있는 시간

    // 2. 시작점 처리
    queue<int> q;
    cost[N] = 0;
    q.push(N);

    // 3. bfs
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        // 앞으로 걷기
        if(cur+1<MAX && cost[cur]+1<=cost[cur+1]){
            if(cur+1==K) (cost[cur]+1 == cost[cur+1]) ? cnt++ : cnt=1;
            else q.push(cur + 1);
            cost[cur + 1] = cost[cur] + 1;
        }

        // 뒤로 걷기
        if(0<=cur-1 && cost[cur]+1<=cost[cur-1]){
            if(cur-1==K) (cost[cur]+1 == cost[cur-1]) ? cnt++ : cnt=1;
            else q.push(cur - 1);
            cost[cur - 1] = cost[cur] + 1;
        }

        // 순간이동
        if(cur*2<MAX && cost[cur]+1<=cost[cur*2]){
            if(cur*2==K) (cost[cur]+1 == cost[cur*2]) ? cnt++ : cnt=1;
            else q.push(cur * 2);
            cost[cur * 2] = cost[cur] + 1;
        }
    }

    // 4. 정답 출력
    cout << cost[K] << "\n" << cnt;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("../test/input.txt", "r", stdin);
    input();
    solve();
}