BOJ - 1916 최소비용 구하기

시작 지점부터 끝 지점 까지 가는 최소비용을 구하는 문제이다.

문제풀이 전략
각 지점들이 연결되어 있는 그래프이고, 각 간선의 가중치가 주어져 있다.

시작 지점으로 부터 여러 지점을 거쳐 끝 지점 까지 도착하는데 필요한 최소 비용을 구해야 한다.

다익스트라 알고리즘을 활용하면 최소 비용을 구할 수 있다.

다익스트라 알고리즘의 핵심은 현재 시작점과 연결되어 있는 끝 노드들로 부터 갈 수 있는 모든 경로 중 최소값을 구하는 것이다.

매 노드마다 최소값을 구하게 되면 시간복잡도가 O(n^2)이 된다.

이 과정을 heap을 사용한다면 heap을 만드는 데 O(logn)이 들고, 이 과정이 간선의 개수만큼 반복되므로 총 시간복잡도는 O(Elogn)이 된다.

우선순위 큐를 활용하여 다익스트라 알고리즘을 적용하면 문제를 해결할 수 있다.

while문 안의 조건문은 다음과 같다.
1. 현재까지 누적된 비용이 현재까지 구해진 종료 지점까지의 비용보다 크면 더이상 진행 할 필요가 없음
2. 다음 노드 까지의 비용이 이미 구해져 있고, 구한 비용보다 작으면 진행할 필요 없음

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> v(n+1);
    vector<int> cost(n+1, 2147000000);

    for(int i=0;i<m;i++){
        int s,e,d;
        cin >> s >> e >> d;
        v[s].push_back(make_pair(d,e));
    }

    int start,end;
    cin >> start >> end;

    priority_queue<pair<int,int>> q;
    cost[start] = 0;
    q.push(make_pair(0,start));

    while(!q.empty()){
        int dist = -q.top().first;
        int cur = q.top().second;
        q.pop();
        if(dist > cost[end])
            continue;
        for(int i=0;i<v[cur].size();i++){
            int next = v[cur][i].second;
            int dt = v[cur][i].first + dist;
            if(cost[next] <= dt)
                continue;
            cost[next] = dt;
            q.push(make_pair(-cost[next], next));
        }
    }

    cout << cost[end];

    return 0;
}

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

회고
문제 풀 때 메모리초과가 계속 발생하였다.
두번째 조건문에 =을 안붙여 생긴 문제였다.
좀 더 조건에 신경쓰며 문제푸는 습관을 들여야 겠다.
그리고 다익스트라 알고리즘에 대한 이해도 부족으로 구현에 어려움을 겪었다.