[C++][백준 13549] 숨바꼭질 3

[문제]

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

13549번: 숨바꼭질 3

[문제 풀이]

우선순위큐를 이용해서 문제를 풀었었다.

문제에서 *2배를 할 경우에는 시간이 지나지 않는다고 했으니 우선순위큐를 pair로 만든 뒤에 시간을 기준으로 정렬을 하자.

*우선순위 큐에서 제일 앞에 있는(시간이 0부터 적은 위치)가 하나씩 빠지니 목표에 도착하는 순간 가장 작은 값이 나온다. 문제를 풀다가 전부 가야한다고 헷갈려서 해당 조건을 빼니 10%에서 계속 틀렸습니다가 발생하였다.

*현재 코드는 헷갈려서 보기가 어려운 부분이 있다. 가독성이 좋게 나중에 고치도록 하자.

 

조건을 하나씩 계속 헷갈려서 많이 틀렸다... 앞으로는 제대로 주의하도록 하자.

[코드]

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int visited[200001];
int brother[200001];
int n,k;
int answer = 99999;

//0초 이동이 언제나 가장 빠르게 선행되어야 한다.

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;

    subin.push(make_pair(n,0) );
    visited[n] = 1;
    brother[n] = 1;

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

        if(curX == k){
            answer = curT;
            return;
        }

        if(curX + 1 <= 100000){
            //1. 방문을 하지 않았을 경우
            //2. 방문을 하였지만 방문했었을때보다 현재 경우가 더 작은 경우.

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

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

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

    return;
}

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

    cout<<answer<<endl;

    return 0;
}