[백준 13549번] 숨바꼭질 3(C++, priority_queue<pair>정렬)

처음엔 priority_queue의 pair.first 기준으로만 정렬하면 되는줄알구 -weight로 넣었는데, 뒤에꺼까지 정렬해야해서

struct cmp를 만들어서 정렬시켰는데,

최대힙을 기준으로 만들어져 있어서 그런가, 부등호 방향을 반대로 해야 제대로 둘다 오름차순으로 정렬되었다.

C++풀이

#include <bits/stdc++.h>

using namespace std;
bool visited[100001];
int N,K;

//음.. 부등호가 왜 반대가 되야할까
// priority_queue가 기본적으로 최대힙으로 되어있어서 그런걸까
struct cmp{
    bool operator()(pair<int,int>& a, pair<int,int>& b)
    {
        if(a.first == b.first)
        {
            return a.second > b.second;
        }else{
            return a.first > b.first;
        }
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>> ,cmp> q; // <val, index>
void dijkstra()
{
	//최초 시작지점 설정.
    q.push({0,N});
    visited[N] = true;

    while(!q.empty())
    {
    	//weight와 idx를 가져옴
        int weight = q.top().first;
        int idx = q.top().second;
        q.pop();
        
        //동생 위치에 도착하면 weight출력하고 종료.
        if(idx ==K) {
            cout << weight;
            return;
        }
        
        // 순간이동 범위내고, 방문한적 없으면 queue에 push
        if(idx*2 <=100000 &&visited[idx*2] == false){
            q.push({weight,idx*2});
            visited[idx*2] = true;
        }
        //뒤로 한칸 가보는거
        if(idx-1 >=0 && visited[idx-1] == false)
        {
            q.push({weight+1,idx-1});
            visited[idx-1] = true;
        }
        //앞으로 한칸 가보는거.
        if(idx+1 <=100000 && visited[idx+1]==false){
            q.push({(weight+1),idx+1});
            visited[idx+1] = true;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    dijkstra();
    
}