[C++][백준 12851] 숨바꼭질 2

[문제]

12851번: 숨바꼭질 2 (acmicpc.net)

12851번: 숨바꼭질 2

[문제 풀이]

수빈이의 현재 위치에서 X +1 , X - 1, X * 2로 이동할때마다 시간이 1씩 추가가 되는 문제이다.

bfs를 이용해서 가장 빨리 도착할 경우가 총 몇가지인지를 구해주자.

 

총 몇가지인지 구해주자고 하지만 가장 빨리 도착하는 경우이므로 pair를 이용해서 시간을 기록한 뒤에 가장 빨리 도착했을 때의 시간과 달라진다면 바로 종료가 되게 만들면 된다.

priority queue(우선순위 큐)를 이용해서 풀었지만 우선순위 큐가 아니라 기본적인 큐를 이용해서 풀더라도 문제가 없다. (숨바꼭질 3에서는 X * 2 와 X + 1, X - 1이 지나는 시간이 달랐지만 해당 문제에서는 동일하므로 큐만으로도 충분하다.)

 

*visited를 제거하면 메모리 초과가 걸리고 그렇다고 visited를 이용해서 매번 체크를 다 할 경우에는 n가지의 경우를 모두 구할 수가 없다. 그렇기에 이미 방문했던 위치의 시간과 방문할 위치의 시간이 다르다면 방문을 하지 않고 같다면 방문을 하게 만들었다.

[코드]

#include <iostream>
#include <queue>

using namespace std;

int n,k;
pair<int, int> answer;
int visited[1000001];

struct compare{
    bool operator()(pair<int, int> a, pair<int, int> b){
        return a.second > b.second;
    }
};


void bfs(){

    priority_queue<pair<int, int>, vector<pair<int, int> >, compare> subin;
    visited[n] = 1;
    subin.push(make_pair(n,0));

    int flag = 0;

    while(subin.size() > 0){
        int curX = subin.top().first;
        int curT = subin.top().second;
        subin.pop();

        if(curX == k){
            answer.first = curT;
            answer.second++;
            flag = curT;
        }

        if(flag != 0 ){
            if(flag != curT){
                return;
            }
        }

        if(curX + 1 <= 100000){
            if(visited[curX + 1] == 0){
                visited[curX + 1] = curT + 1;
                subin.push(make_pair(curX + 1, curT + 1));
            }
            else if(visited[curX + 1] == curT + 1){
                subin.push(make_pair(curX + 1, curT + 1));
            }
        }

        if(curX - 1 >= 0){
            if(visited[curX - 1] == 0){
                visited[curX - 1] = curT + 1;
                subin.push(make_pair(curX - 1, curT + 1));
            }
            else if(visited[curX - 1] == curT + 1){
                subin.push(make_pair(curX - 1, curT + 1));
            }
        }

        if(curX * 2 <= 100000){
            if(visited[curX * 2] == 0){
                visited[curX * 2] = curT + 1;
                subin.push(make_pair(curX * 2, curT + 1));
            }
            else if(visited[curX * 2] == curT + 1){
                subin.push(make_pair(curX * 2, curT + 1));
            }
        }
    }


    return;
}

int main(){
    cin>>n>>k;

    bfs();

    cout<<answer.first<<endl;
    cout<<answer.second<<endl;

    return 0;
}