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

1.문제 링크

숨바꼭질 3

2. 풀이 전 계획과 생각

• 최단경로

3. 풀이

#include<iostream>
#include<queue>
#define INF 987654321
using namespace std;

int Dist[100001];

// 다익스트라 알고리즘  
void dijkstra(int start){
    priority_queue<pair<int , int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    pq.push({0,start});
    Dist[start]=0;

    while(!pq.empty()){
        int dist = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if(Dist[now]<dist) continue;
        
        int next, cost;
        

		
        next = now-1;
        if(!(next < 0 || next > 100000)){
        	cost = dist+1;
        	if(cost<Dist[next]){
            	Dist[next]=cost;
            	pq.push({cost, next});
        	}	
		}

        next = now+1;
        if(!(next < 0 || next > 100000)) {
        	cost = dist + 1;
        	if(cost<Dist[next]) {
            	Dist[next]=cost;
            	pq.push({cost, next});
        	} 
		}
        cost = dist+1;
      
        next = now*2;
        if(!(next < 0 || next > 100000)){
        	cost = dist;
        	if(cost<Dist[next]){ 
            	Dist[next]=cost;
            	pq.push({cost, next});
        	}
		}
    }
}

int main(){
    int n, k; 
    cin>>n>>k;
    
    for(int i=0;i<100001;i++) Dist[i]=INF;
    
    dijkstra(n);
    
    cout<<Dist[k];
}

일반적인 그래프의 다익스트라 알고리즘 코드에서 아이디어를 얻어 현재 위치에서 +1, -1, *2를 했다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• 다익스트라 알고리즘에 대한 이해도가 올라감

• 새로운 형태에서의 다익스트라 알고리즘 일반적인 그래프 형태가 형태에서 다익스트라 알고리즘을 적용해봄.