백준 1916번 - 최소비용 구하기

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

얼마 전에 플로이드 와샬 문제를 풀면서 다익스트라가 기억이 안 났었다.
다시 알고리즘 책을 보면서 이 문제를 되짚어 보았다.



먼저 다익스트라 알고리즘은 그리디 문제 해결법의 종류 중에 하나로
시작 정점을 기준으로 각각의 정점에 대해 최단 거리를 구할 때 쓰이는 알고리즘이다. 
문제를 보면 출발 도시와 도착 도시가 주어지고 최소 비용을 구하면 되기 때문에 
다익스트라 알고리즘을 적용하면 된다. 

우선순위 큐로 풀 수도 있지만 
정점이 1000개 이기 때문에 O(N^2)안에 배열을 이용하여 풀 수 있도록 했다.




다익스트라의 문제 해결법은
시작 정점이 있을 때 시작 정점과 다른 정점들 간의 거리를 먼저 설정을 한다. 
시작 정점을 1이라고 해보자.


그다음으로 시작 정점에서 가장 가까운 거리에 있는 정점을 찾아야 하는데 이를 vnear이라고 해보자.
그리고 vnear을 2라고 해보자.


이때 다른 정점이 3이 있다고 한다면
1에서 3까지의 거리와 1에서 vnear까지의 거리 + vnear에서 3까지의 거리를 비교한 후에 
vnear를 거쳐서 3으로 가는 것이 더 빠르다면 새로운 거리를 업데이트해주면 된다.
그리고 이 과정을 4와 5에 대해서 반복하여 업데이트해주면 된다.


vnear을 구하는 이유는 시작 정점에서 가장 가까운 정점(vnear)을 거쳐서 새로운 정점까지의 거리가 
시작 정점에서 새로운 정점까지의 거리보다 가까울 수 있기 때문이다. 



이렇게 vnear을 구할 때마다 visited로 방문했음을 체크하고 아직 방문하지 않은 정점 중에서 
vnear을 구하면서 위의 작업을 반복해주면 된다. 


위의 과정을 직접 그림으로 그려보았는데 순서대로
vnear이 v2 -> v3 -> v4 -> v5로 변경되면서 
v1에서 각각의 정점 간에 거리가 업데이트 되는 것을 볼 수 있다.

 

 

 

 

 

 

위의 그림은 vnear가 v2일 때 v3, v4, v5가 업데이트 되는 모습이다.

 

 

 

 

위의 그림은 vnear가 v3 일 때 v4, v5가 업데이트 되는 모습이다.

 

 

 

 

위의 그림은 vnear가 v4일 때 v5가 업데이트 되는 모습이다.

 

 

 

 

위의 그림은 vnear가 v5 일 때 종료되는 모습이다.

 

 

 

문제를 풀 때 먼저 W라는 이차원 배열을 통해 정점과 정점 간의 거리를 굉장히 큰 값으로 지정한 뒤에 
입력에서 주어지는 거리에 따라 다시 바꿔주도록 했다.



그다음으로 dist라는 배열을 통해서 시작 정점에서 각각의 정점별로 거리 값을 구할 수 있도록 했다.
(ex/ dist[1]= 시작 정점과 '1' 정점의 거리, dist[2]= 시작 정점과 '정점'의 거리...)


마지막으로 주의할 점은
시작 도시와 도착 도시와 비용이 주어질 때 
시작 도시와 도착 도시가 같은데 비용이 다르게 주어지는 경우가 있다. 
 이 부분만 주의해 주면 된다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,m;
int inf=0xfffffff;
vector<vector<int>> W;
 
void dijkstra(int start,int end){
    
    vector<bool> visited(n+1,false);
    vector<int> dist(n+1,inf);
    
    for(int i=1;i<=n;i++)
        dist[i]=W[start][i];
    
    int cnt=n;
    int vnear=start; //가장 가까운 정점
    visited[start]=true;
    
    while(cnt--){
        
        int min_dist=inf;
        for(int i=1;i<=n;i++){ //vnear 구하기
            if(!visited[i] && min_dist>dist[i]){
                vnear=i;
                min_dist=dist[i];
            }
        }
        
        for(int i=1;i<=n;i++){
            
            //이전에 vnear로 방문했거나 vnear에서 연결된 길 없을 때
            if(visited[i] || W[vnear][i]==inf)
                continue;
            
            //시작 정점에서 i로 가는 길보다 vnear 거쳐 가는길이 더 빠를 때
            if(dist[vnear]+W[vnear][i]<dist[i])
                dist[i]=dist[vnear]+W[vnear][i];
        }
        visited[vnear]=true;
    }
    
    cout<<dist[end]<<endl;
}
int main(){
    
    cin>>n>>m;
    W=vector<vector<int>> (n+1,vector<int>(n+1,inf));
    
    int start,end,cost;
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&start,&end,&cost);
        W[start][end]=min(W[start][end],cost);
    }
    
    scanf("%d %d",&start,&end);
    dijkstra(start,end);
    
    return 0;
}