[백준] 1753 최단 경로 dijkstra

문제 :

www.acmicpc.net/problem/1753

1753번: 최단경로

 

분석 :

대표적인 다익스트라 알고리즘 문제이다. 

다익스트라의 방향 그래프를 구현하기 위해서 배열 또는 우선순위 큐 자료구조를 사용한다.

배열로 사용 할 시 시작 노드와 끝나는 노드의 가중치를 넣기 위해 

int v[in][to] = w 와 같이 사용해야 하는데

문제의 배열의 범위가 20000이라 시간 초과가 나 사용이 불가능 했다. 이는 모든 노드들에 대해 for문을 돌면서 또 다시 for문을 돌아 최단 거리를 찾아야 하기 때문에 시간 복잡도가 O(V(vertex) ^2)의 시간이 걸린다.

 

하지만 우선 순위 큐를 이용한다면 바로 pop 시 거리가 가장 큰 (우리가 원하는 것은 거리가 가장 작은 노드이므로 - 붙여준다)

노드를 바로 찾아주기 때문에 O(E(edge))시간 만큼만 걸린다는 걸 알 수 있다. (모든 edge를 한번씩 돈다 ..!)

그래서 다른 블로그들의 도움을 받아 우선 순위 큐를 활용해 거리가 작은 노드부터 꺼내 최단 거리를 계산해 주었다. 

 

 

c++ 코드 :

//
//  1753_min_path.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/09.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define INF 1e9

vector<pair<int, int>> vertex[100001];
int d[100001]; // 최단 거리 테이블

void find_min_path(int start){
    priority_queue<pair<int, int>>pq;
    //거리, 까지 정점
    pq.push(make_pair(0, start));
    d[start] = 0;
    
    while(!pq.empty()){
        //우선 순위 큐는 가장 큰 원소 top으로 놓으므로
        //거리 작은 정점부터 꺼내지도록 하기
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < vertex[now].size(); i++){
            //거쳐서 가는 노드의 비용을 계산
            int cost = dist + vertex[now][i].second;
            if(cost <d[vertex[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[vertex[now][i].first] = cost;
                pq.push(make_pair(-cost,vertex[now][i].first));
            }
        }
    }
}

int main(){
    int v, e;
    cin >> v >> e;
    int start;
    cin >> start;
    
    for(int i =0; i < e; i++){
        int in, to, w;
        cin >> in >> to >> w;
        vertex[in].push_back({to, w});
    }
    fill(d, d+100001, INF);
    find_min_path(start);
    
    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= v; i++)
    {
        // 도달할 수 없는 경우
        if (d[i] == INF) {
            cout << "INF" << '\n';
        }
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }

    return 0;
}