[c++] BOJ 1916 :: 최소비용 구하기

난이도 : 골드 5

걸린 시간 : 30분

 

문제

최소비용 구하기 문제 바로가기

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

풀이

• 다익스트라 기본 구현을 이용해서 푼다.
• 다익스트라 개념 바로가기

 

코드

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

using namespace std;

int main() {
    // 최소비용 문제 => bfs / 그래프 탐색(다익스트라)
    // N 10^3이하 M 10^6 이하
    // 출발, 도착, 비용
    // 비용 10^6 이하
    // 마지막 (출발, 도착)

    // 다익스트라로 풀면,
    // 출발 => (비용, 도착) priority_queue에 저장
    // 최소 간선 하나씩 빼면서 갱신

    // 입력
    int N; int M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> bus(N + 1); // 비용, 도착 저장
    vector<int> memo(N + 1, 1e9);
    for (int i = 0; i < M; i++) {
        int s, e, v;
        cin >> s >> e >> v;
        bus[s].push_back(make_pair(v, e));
    }

    int start; int target;
    cin >> start >> target;

    priority_queue<pair<int, int>> que;
    que.push(make_pair(0, start));

    while (!que.empty()) {
        pair<int,int> tmp = que.top();
        int v = -tmp.first; int e = tmp.second;
        que.pop();
        if (v > memo[e]) // 현재 value가 memo[e] 보다 크다면 이미 최소 값으로 갱신 된 곳이기 때문에 할 필요 없음
            continue;

        for (int i = 0; i < bus[e].size(); i++) {
            pair<int, int> tmp2 = bus[e][i];
            int value = tmp2.first; int end = tmp2.second;
            if (value + v < memo[end]) {
                memo[end] = value + v;
                que.push(make_pair(-memo[end], end));
            }
        }
    }

    cout << memo[target] << endl;
}

 

결과

 

생각해볼 것

• 다익스트라는 시작점에서 모든 점까지의 최소 비용을 계산해주기 때문에 필요없는 정보도 들어있다.
• 다양한 최단거리 측정 알고리즘
  • BFS : 가중치가 없을 경우(주로), 1:N
    • 큐를 이용하여 순차적으로 체크하면서 노드의 가중치 갱신
    • O(V+E)
  • 다익스트라 : 가중치가 양수인 경우, 1:N
    • 우선순위 큐를 이용하여 가중치가 낮은 간선부터 체크하면서 노드의 가중치 갱신
    • 다익스트라는 음수의 가중치를 가진 cycle에서 음의 무한대로 발산하므로 최소값을 정할 수 없음
      • queue를 통해 무한대로 루프가 돌아감
      • 반면 벨만-포드는 정해진 횟수만 동작하기 때문에 무한대 x
    • O(ElogE)

S부터 E까지의 최소 경로는 음의 무한대로 발산함

• • 벨만-포드 : 가중치가 음수인 경우도 가능, 1:N
    • 모든 엣지를 돌면서 노드의 가중치를 갱신하는 과정을 모든 엣지의 갯수만큼 수행 => 아직 가중치가 초기값일 수도 있기 때문 (초기값이면 로직 수행 x)
    • 다익스트라보다 느림 O(VE)
  • Shortest Path Faster Algorithm (SPFA) : 벨만포드 향상 알고리즘
  • 플로이드 와샬 : N:N
    • dk(i,j)=min(dk−1(i,j),dk−1(i,k)+dk−1(k,j))
    • O(V^3)

 

참고 : https://shnoh.tistory.com/15

https://www.crocus.co.kr/1089