1916번 최소비용 구하기

Posted Aug 10, 2025

By matin1202

6 min read

1916번 최소비용 구하기

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

풀이

1916번 최소비용 구하기 문제는 N개의 도시와 M개의 버스 노선이 주어졌을 때, 특정 시작 도시에서 도착 도시까지 가는 데 드는 최소 비용을 구하는 문제입니다. 모든 버스 노선은 비용(가중치)을 가지며, 비용은 양수입니다. 이는 전형적인 단일 시작점 최단 경로 문제이며, 간선의 가중치가 모두 양수이므로 다익스트라(Dijkstra) 알고리즘을 사용하여 해결할 수 있습니다.

다익스트라 알고리즘 접근 방식:

자료 구조:
- 인접 리스트: 그래프의 연결 상태를 저장하기 위해 vector<vector<pair<int, int>>> g 형태의 인접 리스트를 사용합니다. g[u]는 u에서 출발하는 간선들을 저장하며, 각 간선은 {목적지 노드 v, 가중치 w}의 쌍으로 표현됩니다. (여기서는 g[u-1].push_back({v-1, w})와 같이 0base-인덱스로 처리합니다.)
- 거리 배열: vector<int> dist는 시작 노드로부터 각 노드까지의 최소 거리를 저장합니다. 처음에는 시작 노드를 제외한 모든 노드의 거리를 무한대(INF)로 초기화합니다.
- 우선순위 큐: 다음에 방문할 노드를 효율적으로 선택하기 위해 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq를 사용합니다. 큐에는 {현재까지의 거리, 노드 번호} 쌍을 저장하며, greater를 사용하여 거리가 가장 작은 노드가 우선적으로 추출되도록 합니다. (최소 힙).
초기화:
- 시작 노드 s의 dist[s]를 0으로 설정하고, 우선순위 큐에 {0, s}를 삽입합니다.
- 나머지 모든 노드 i에 대해 dist[i]를 INF로 초기화합니다.
탐색 과정:
- 우선순위 큐가 빌 때까지 다음을 반복합니다:
  1. 큐에서 (d, u)를 꺼냅니다. 여기서 d는 시작 노드로부터 u까지의 현재까지 발견된 최소 거리이고, u는 노드 번호입니다.\n
  2. 만약 d가 이미 dist[u]에 저장된 값보다 크다면 (이미 더 짧은 경로를 찾아서 처리했으므로), 현재 (d, u)는 무시하고 다음 요소를 처리합니다. 이는 중복된 경로 탐색을 방지하는 효율적인 방법입니다.\n
  3. u에 연결된 모든 인접 노드 v와 해당 간선의 가중치 w에 대해 다음을 수행합니다:\n
    - dist[u] + w (현재 노드 u를 거쳐 v로 가는 새로운 경로의 비용)가 dist[v] (기존에 알려진 v까지의 최소 비용)보다 작다면,\n
    - dist[v]를 dist[u] + w로 업데이트하고,\n
    - 우선순위 큐에 {dist[v], v}를 삽입합니다. 이로써 v에 대한 새로운 더 짧은 경로가 발견되었음을 알리고, 나중에 이 경로를 통해 v의 이웃 노드를 탐색할 수 있게 합니다.
결과:
- 탐색이 완료되면, dist[e]에는 시작 노드 s에서 도착 노드 e까지의 최소 비용이 저장됩니다.

시간 복잡도: 다익스트라 알고리즘의 시간 복잡도는 우선순위 큐를 사용할 경우 $O(E \log V)$ 또는 $O(E + V \log V)$입니다. 여기서 V는 도시의 수(정점), E는 버스 노선의 수(간선)입니다. 문제에서는 도시의 수를 N, 버스 노선의 수를 M으로 정의했으므로, $O(M \log N)$이 됩니다. 각 간선에 대해 최대 한 번 push 및 pop 연산이 일어나며, 이 연산들은 $O(\log V)$의 시간이 소요됩니다.

공간 복잡도: 그래프를 인접 리스트로 저장하기 위해 $O(V + E)$의 공간이 필요하며, 거리 배열 dist에 $O(V)$, 우선순위 큐에 최대 $O(V)$의 공간이 필요하므로, 총 공간 복잡도는 $O(V + E)$ 또는 $O(N + M)$입니다.

코드

1916.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 987654321;
void dijstra(const vector<vector<pair<int, int>>>& g, int s, int e){
    int N = g.size();
    vector<int> dist(N, INF);
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(dist[u] < d) continue;
        for(auto [v, w] : g[u]){
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    cout << dist[e] << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    auto g = vector(N, vector<pair<int, int>>());
    for(int i = 0; i < M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u-1].push_back({v-1, w});
    }
    int s, e;
    cin >> s >> e;
    dijstra(g, s-1, e-1);
    return 0;
}

Standard Input (stdin):

C++

BaekJoon

This post is licensed under CC BY 4.0 by the author.

풀이

코드

Trending Tags