[백준 1753] 최단 경로

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

1753번: 최단경로

다익스트라를 적용하는 대표적인 문제입니다.

문제를 풀기위해서라기보단 다익스트라 구현을 적으면서 내용을 정리해보고싶어서 글을 작성합니다.

 

먼저 최단 경로를 구하는 알고리즘은 여러가지가 있습니다.

그 중에 용도에 따라 자주 쓰이는 알고리즘은 다익스트라, 벨만-포드, 플루이드-워셜 알고리즘이 있습니다.

 

다익스트라	특정 정점에서 나머지 정점의로의 최단 경로를 구하는 방법. 간선의 가중치가 음수이면 사용이 불가능하다
벨만-포드	특정 정점에서 나머지 정점의로의 최단 경로를 구하는 방법. 간선의 가중치가 음수여도 사용이 가능하다
플루이드-워셜	모든 정점에서 모든 정점으로의 최단 경로를 구하는 방법

 

이 특징들 이외에도 시간복잡도 등의 특성이 있겠지만 기능상의 내용만 표에는 서술했습니다.

 

1753번 문제는 특정 정점에서 나머지 정점으로의 최단경로만을 요구하고 간선의 가중치가 양수이므로 다익스트라가 적합합니다.

 

제가 애용하는건 기본 로직보다 조금 더 간단한 우선순위 큐(최소 힙)을 이용한 구현이므로 우선순위 큐를 이용하겠습니다.

 

0. 주어진  V에 해당하는 만큼의 크기의 최단 경로를 저장할 int형 배열 d를 선언하고 각 방에 문제에서 만들 수 있는 가장 큰 가중치의 합을 넣는다.

(저는 INT_MAX를 이용해 int의 최대값을 넣었습니다.) 

 

1. 입력의 3번째 줄부터 주어지는 정보(u에서 v로 가는 가중치 w인 간선)를 이용해 각 시작(u) 정점의 백터에 목표(v)정점의 번호와 가중치(w)를 넣습니다. 

 

2. 최초 시작 정점인 K의 백터에서 갈 수 있는 정점과 가중치의 정보를 가중치가 최소로 나올 수 있게 최소힙에 모두 넣습니다.

 

3.  우선순위 큐에서 최소값을 꺼내고 해당 최소값을 가진 목표 정점이 아직 최단경로가 갱신되지 않은상태(INT_MAX)이면 최단경로를 꺼낸 최소값으로 설정합니다.

(만약 최단경로가 갱신되어있다면 5번 동작을 합니다.)

 

4. 그리고 해당 목표 정점이 연결된 모든 간선의 정보를 2번 내용과 같이 집어넣습니다.

 

5. 3~4번의 동작을 최소힙이 빌 때까지 반복합니다.

 

6. 최소 힙이 비게 되면 최단 경로가 저장된 배열 d를 돌면서 결과를 출력합니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int V,E,K,d[20002];
vector<pair<int,int>> v[20002];
priority_queue<pair<int,int>> pq;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> V >> E >> K;
    for(int i=1;i<=V;i++) d[i]=INT_MAX; 
    for(int i=0;i<E;i++)
    {
        int a,b,c; cin >> a >> b >> c;
        v[a].push_back({c,b});
        if(a==K) pq.push({-1*c,b});
    }

    while(!pq.empty())
    {
        int to = pq.top().second, dis=-1*pq.top().first; pq.pop();
        if(d[to]==INT_MAX)
        {
            d[to]=dis;
            for(int i=0;i<v[to].size();i++)
            {
                int new_dis = dis+v[to][i].first;
                int new_to = v[to][i].second;
                pq.push({-1*new_dis,new_to});
            }
        }
    }
    for(int i=1;i<=V;i++)
    {
        if(i==K) cout << 0<<endl;
        else if(d[i]==INT_MAX) cout << "INF" << endl;
        else cout << d[i]<<endl;
    }
}