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

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

---

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

문제 설명:

n개의 도시와 m개의 버스가 주어질 때, 특정 시작 도시에서 특정 도착 도시까지의 최소 비용을 구하고, 그 경로를 출력하는 문제입니다.

입력:

• 첫째 줄에 도시의 개수 n (1 ≤ n ≤ 1,000)과 버스의 개수 m (1 ≤ m ≤ 100,000)이 주어집니다.
• 다음 m개의 줄에는 세 개의 정수 a, b, cost가 주어지며, 이는 도시 a에서 도시 b로 가는 비용이 cost임을 의미합니다.
• 마지막 줄에는 출발 도시와 도착 도시가 주어집니다.

출력:

• 첫째 줄에 최소 비용을 출력합니다.
• 둘째 줄에 최소 비용으로 이동하기 위한 경로에 포함된 도시의 개수를 출력합니다.
• 셋째 줄에 최소 비용 경로에 포함된 도시를 순서대로 출력합니다.

---

문제 해결 코드

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

const int INF = 1e9;
vector<pair<int, int>> graph[1001];
int dist[1001];
int parent[1001];

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (dist[current] < currentDist) continue;

        for (auto edge : graph[current]) {
            int next = edge.first;
            int cost = edge.second;

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

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

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

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }

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

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

    dijkstra(start);

    // 최소 비용 출력
    cout << dist[end] << '\n';

    // 경로 추적
    stack path;
    for (int current = end; current != 0; current = parent[current]) {
        path.push(current);
    }

    // 경로에 포함된 도시 개수 출력
    cout << path.size() << '\n';

    // 경로 출력
    while (!path.empty()) {
        cout << path.top() << ' ';
        path.pop();
    }

    return 0;
}

예제

입력:
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
4
1 3 4 5

---

코드 설명

• 다익스트라 알고리즘:
  • 우선순위 큐를 이용해 최단 경로를 계산합니다.
  • 도시 i까지의 최단 거리를 dist[i]에 저장합니다.
  • 도시 i로 이동하기 직전의 도시를 parent[i]에 저장합니다.
• 경로 추적:
  • 도착 도시에서 시작하여 parent를 따라가며 경로를 스택에 저장합니다.
  • 스택에 저장된 경로를 역순으로 출력합니다.

시간 복잡도

• 다익스트라 알고리즘: O((n + m) log n)
• 경로 추적: O(n)
• 전체 시간 복잡도는 O((n + m) log n)로, 입력 크기에 대해 효율적입니다.

---

결과

코드는 최소 비용과 해당 경로를 정확히 계산하며, 다익스트라 알고리즘을 통해 효율적으로 구현되었습니다. 입력 크기가 커져도 빠르게 동작합니다.

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