[C/C++] 백준 #1916 최소비용 구하기(다익스트라)

이번 문제는 다익스트라 알고리즘을 이용해서 최소 경로를 구하는 문제입니다.

 

Edsger W. Dijkstra

 

다익스트라 알고리즘은 Edsger W. Dijkstra(독일 : 데이크스트라 또는 다이크스트라)가 개발한 알고리즘입니다.  프림 알고리즘과 비슷하지만, 누적 간선 가중치의 값을 노드의 값으로 한다는 점이 다릅니다.  DFS, 프림, 다익스트라, A* 알고리즘은 모두 비슷한 형태로 구성이 되어서 이해하면 쉽게 구현이 가능합니다.

 

다익스트라를 구현하는 방법은 거의 일정합니다.  다익스트라 기본 알고리즘은 시작정이 주어지고, 나머지 모든 노드들까지의 최소 경로값을 구하는 것이지만, 여기서는 도착점이 주어지기 때문에, 도착점이 선택되면, 그 부분에서 멈추도록 합니다.

 

이 문제에서는 저는 인접행렬과 힙을 이용해서 구현해보았습니다.  일반적으로는 인접리스트와 힙을 이용하는 것이 기본입니다.  문제 자체는 인접행렬보다는 인접리스트로 구현하는 것이 더 좋습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//    baekjoon #1916
//        - by Aubrey Choi
//        - created at 2019-09-29
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>
#define    MAXINT    0x7fffffff

struct Node { int i, v; } q[5000];
bool cmp(Node &a, Node &b) { return a.v>b.v; }
int main()
{
    static int adj[1000][1000], v[1000];
    int n, m, s, e, t, qp=1;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) { v[i]=MAXINT; for(int j=0;j<n;j++) adj[i][j]=MAXINT; }
    while(m--)
    {
        int f, t, w;
        scanf("%d%d%d",&f,&t,&w);
        if(adj[f-1][t-1]>w) adj[f-1][t-1]=w;
    }
    scanf("%d%d",&s,&e); s--,e--;
    q[0].i=s; q[0].v=0; v[s]=0;
    for(;;)
    {
        std::pop_heap(q, q+qp--, cmp);
        s=q[qp].i, t=q[qp].v;
        if(s==e) break;
        if(v[s]!=t) continue;
        for(int i=0;i<n;i++)
        {
            if(adj[s][i]==MAXINT||t+adj[s][i] >= v[i]) continue;
            v[i]=t+adj[s][i];
            q[qp].i=i, q[qp].v=v[i]; qp++;
            std::push_heap(q, q+qp, cmp);
        }
    }
    printf("%d\n", t);
}