백준 2406번 [안정적인 네트워크](C++) -yes6686- 티스토리

백준 문제 풀이: 2406 [안정적인 네트워크]

---

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

문제 설명:

주어진 컴퓨터 네트워크에서 안정적인 네트워크를 구성하기 위해 최소 비용으로 추가해야 할 연결들을 구하는 문제입니다. 초기 연결 상태가 주어지고, 각 컴퓨터 쌍의 연결 비용이 주어질 때, 추가로 연결해야 할 최소 비용과 연결 목록을 출력합니다.

네트워크 안정성을 유지하기 위해 모든 컴퓨터가 하나의 네트워크로 연결되어야 합니다.

---

문제 해결 코드

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

int parent[1001]; // 각 노드의 부모를 저장하는 배열
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;

int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

bool isSameParent(int a, int b) {
    return findParent(a) == findParent(b);
}

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

    int n, m; // 컴퓨터 수와 초기 연결된 간선 수
    cin >> n >> m;

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

    // 초기 연결 상태를 입력받아 union 연산 수행
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        unionParent(u, v);
    }

    // 비용 정보를 입력받아 우선순위 큐에 저장
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int cost;
            cin >> cost;
            if (i != j) {
                pq.push({cost, {i, j}});
            }
        }
    }

    int totalCost = 0; // 최소 비용
    int pairCount = 0; // 추가 연결된 쌍의 개수
    queue<pair<int, int>> result; // 연결된 컴퓨터 쌍을 저장

    // 최소 스패닝 트리(MST) 알고리즘
    while (!pq.empty()) {
        int cost = pq.top().first;
        int u = pq.top().second.first;
        int v = pq.top().second.second;
        pq.pop();

        if (!isSameParent(u, v)) {
            unionParent(u, v);
            totalCost += cost;
            pairCount++;
            result.push({u, v});
        }
    }

    // 결과 출력
    cout << totalCost << ' ' << pairCount << '\n';
    while (!result.empty()) {
        cout << result.front().first << ' ' << result.front().second << '\n';
        result.pop();
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구합니다. 초기 연결 상태를 반영하여 이미 연결된 간선은 제외합니다.
• 구현 세부사항:
  • findParent: 노드의 부모를 찾는 함수로, 경로 압축을 사용합니다.
  • unionParent: 두 노드를 같은 집합으로 합칩니다.
  • 우선순위 큐를 사용하여 비용이 작은 간선부터 처리합니다.
• 시간 복잡도 분석:
  • 초기 union 연산: O(M log N), 여기서 M은 초기 연결 간선의 수
  • 크루스칼 알고리즘: O(E log E), 여기서 E는 모든 간선의 수
  전체 시간 복잡도는 O(E log E + M log N)입니다.

---

결과

추가 연결해야 하는 최소 비용과 연결 목록을 정확히 출력합니다. 크루스칼 알고리즘을 활용하여 효율적으로 해결할 수 있습니다.

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