백준 1916번 [최소비용 구하기](C++) -yes6686- 티스토리

백준 문제 풀이: 1916 [최소비용 구하기]

---

문제 링크: https://www.acmicpc.net/problem/1916

문제 설명:

n개의 도시가 주어졌을 때, 출발 도시에서 도착 도시로 가는 최소 비용을 구하는 문제입니다. 각 도시는 버스로 연결되어 있으며, 비용이 다릅니다.

입력:

• 첫 번째 줄에 도시의 개수 n (1 ≤ n ≤ 1,000)와 버스의 개수 m (1 ≤ m ≤ 100,000)가 주어집니다.
• 다음 m개의 줄에는 버스의 출발 도시 a, 도착 도시 b, 비용 c가 주어집니다. (1 ≤ c ≤ 100,000)
• 마지막 줄에는 출발 도시 start와 도착 도시 last가 주어집니다.

출력:

• 출발 도시에서 도착 도시로 가는 데 드는 최소 비용을 출력합니다.

예제:

입력:
5 8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

출력:
4

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9; // 무한대를 나타내는 큰 값
vector<pair<int, int>> graph[1001]; // 인접 리스트
int dist[1001]; // 최단 거리 배열

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(dist, dist + 1001, INF); // 최단 거리 초기화
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if (cost > dist[cur]) continue; // 이미 처리된 거리보다 큰 경우 무시

        for (auto &edge : graph[cur]) {
            int next = edge.first;
            int nextCost = edge.second;

            if (dist[next] > cost + nextCost) {
                dist[next] = cost + nextCost;
                pq.push({dist[next], next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }

    int start, last;
    cin >> start >> last;

    dijkstra(start);

    cout << dist[last] << '\n';
    return 0;
}

---

코드 설명

이 코드는 다익스트라 알고리즘을 사용하여 출발 도시에서 도착 도시까지의 최단 거리를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 다익스트라 알고리즘은 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.
  • 우선순위 큐를 사용하여 현재까지의 최단 경로를 기준으로 확장합니다.
• 구현 세부사항:
  • graph[u].push_back({v, c}): 버스 노선 정보를 그래프의 인접 리스트에 저장합니다.
  • dist[v]: 시작점에서 정점 v까지의 최단 거리를 저장합니다.
  • priority_queue: 현재까지의 최단 거리를 기준으로 정렬하여 처리합니다.
• 시간 복잡도 분석:
  • 간선 수 E, 정점 수 n에 대해 O((n + E) log n)
  • 최대 100,000개의 간선과 1,000개의 정점에 대해 효율적으로 작동합니다.

---

예제

다음은 임의로 생성한 테스트 예제입니다:

입력:
6 9
1 2 2
1 3 5
2 3 2
2 4 1
3 4 3
3 5 1
4 5 6
5 6 2
4 6 4
1 6

출력:
9

이 예제에서는 출발지(1번)에서 목적지(6번)까지의 최소 비용이 9로 계산됩니다.

---

결과

코드는 입력된 도시와 버스 정보를 기반으로 출발 도시에서 도착 도시까지의 최단 비용을 정확히 계산합니다. 다익스트라 알고리즘을 사용하여 효율적으로 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!