[Gold 4] 12851 숨바꼭질 2

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

 

이 문제는 BFS를 사용하면 해결할 수 있다.

 

수빈이가 움직일 수 있는 경우의 수는 3가지다.

뒤로 1칸, 앞으로 1칸, 2배 전진하는 경우이다.

따라서 dir 배열 속에 {-1, 1, 0}을 넣고 0인 경우 2배 전진하도록 한다.

 

현재 위치가 동생의 위치인 경우 최소 시간과 현재 시간을 비교하여

최소 시간이 더 큰 경우 동생을 찾을 수 있는 수를 1로 초기화 하고 최소 시간을 갱신한다.

만약 최소 시간이 현재 시간과 같다면 동생을 찾을 수 있는 수를 1 증가시킨다.

 

#include <iostream>
#include <queue>
using namespace std;

int N, K;
int minTime = 987654321;
int answer = 0;
bool visited[100001];
int dir[3] = {-1, 1, 0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>K;
    queue<pair<int,int>> q;
    q.push({N,0});
    while(!q.empty()){
        int now = q.front().first;
        int time = q.front().second;
        q.pop();
        visited[now] = true;

        if(now == K){
            if(minTime > time){
                minTime = time;
                answer = 1;
            }
            else if(minTime == time)
                answer++;
        }


        for(int i = 0;i<3;i++){
            int next;
            if(dir[i] == 0)
                next = now * 2;
            else
                next = now + dir[i];
            
            if(next > 100000 || next < 0)
                continue;

            if(!visited[next]){
                q.push({next, time + 1});
            }
            
        }
    }
    cout<<minTime<<'\n'<<answer;
}