백준 20010번 [악덕 영주 혜유](C++) -yes6686- 티스토리

백준 문제 풀이: 20010 [악덕 영주 혜유]

---

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

문제 설명:

그래프의 최소 스패닝 트리(MST)를 구성하고, 이를 기반으로 다음 두 가지를 계산하는 문제입니다:

• 최소 스패닝 트리를 구성하는 간선의 총 비용
• 최소 스패닝 트리에서 두 점 사이의 최장 경로

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;

vector<pair<int, int>> adj[1001]; // MST를 저장할 인접 리스트
priority_queue<pair<int, pair<int, int>>, 
    vector<pair<int, pair<int, int>>>, 
    greater<>> pq; // 간선 정보를 저장할 우선순위 큐

int parent[1001]; // 부모를 저장하는 배열
int dist[1001];   // 다익스트라에서의 거리 저장
int maxDist = 0;  // MST에서 최장 경로

// Union-Find 알고리즘 (Find)
int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

// Union-Find 알고리즘 (Union)
void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// MST의 최장 경로 계산 (다익스트라)
void dijkstra(int start, int V) {
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
    }
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq1;
    pq1.push({0, start});

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

        for (auto [ncost, next] : adj[cur]) {
            if (dist[next] > cost + ncost) {
                dist[next] = cost + ncost;
                pq1.push({dist[next], next});
                maxDist = max(maxDist, dist[next]);
            }
        }
    }
}

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

    int V, E; // 정점과 간선의 개수
    cin >> V >> E;

    // 부모 배열 초기화
    for (int i = 0; i < V; i++) {
        parent[i] = i;
    }

    // 간선 입력
    for (int i = 0; i < E; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        pq.push({C, {A, B}});
    }

    int totalCost = 0; // MST의 총 비용

    // 크루스칼 알고리즘으로 MST 구성
    while (!pq.empty()) {
        int cost = pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();

        if (findParent(a) != findParent(b)) {
            unionParent(a, b);
            adj[a].push_back({cost, b});
            adj[b].push_back({cost, a});
            totalCost += cost;
        }
    }

    // MST에서 최장 경로 계산
    for (int i = 0; i < V; i++) {
        dijkstra(i, V);
    }

    // 결과 출력
    cout << totalCost << '\n'; // MST의 총 비용
    cout << maxDist << '\n';  // MST에서의 최장 경로

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용해 MST를 구성하고, 다익스트라 알고리즘으로 MST의 최장 경로를 계산합니다.
• 구현 세부사항:
  • findParent, unionParent: 유니온-파인드 알고리즘을 사용하여 MST를 구성합니다.
  • MST의 간선 정보는 adj 배열에 저장하며, 이후 다익스트라 알고리즘에서 활용합니다.
  • dijkstra: MST에서 특정 노드에서 시작해 최장 경로를 계산합니다.
• 시간 복잡도 분석:
  • 크루스칼 알고리즘: O(E log E)
  • 다익스트라 알고리즘: O(V²)
  전체 시간 복잡도는 O(E log E + V³)입니다.

---

결과

MST의 총 비용과 MST에서의 최장 경로를 정확히 계산합니다. 그래프와 최소 스패닝 트리를 기반으로 최적의 풀이를 제공합니다.

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