[백준 2406번] 안정적인 네트워크

푼 문제

2406번: 안정적인 네트워크

문제 설명

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.
네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다.
회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다.
예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다.
두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.

풀기 전 한 생각

우선 "최소 비용으로 회사의 네트워크가 안정적으로 되도록" 해야 한다고 했고, "두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다"라고 했으므로 MST 문제는 맞다. 그런데 "안정적인 네트워크"를 만드는 게 MST를 만들면 해결될 것 같아 보이기는 한데, 1번 노드가 좀 걸렸다. 1번 노드를 포함해서 연결하기에는 이미 다른 모든 노드들과 연결되어 있고, 또 이 1번 노드 때문에 MST를 만드는 과정에서 사이클이 생기기 쉬워보였다.

결론적으로 말하자면 1번 노드를 제외하고 MST를 해야 한다. 1) 다들 노드들끼리의 간선에서 장애가 발생한 경우, 2) 1번 노드와의 간선에서 장애가 발생한 경우, 3) 다른 노드가 장애가 발생한 경우, 4) 1번 노드가 장애가 발생한 경우 이 4가지 경우의 수를 모두 생각해보면 힌트를 얻을 수 있다. 그리고 1번 노드가 튀는 존재이므로 다른 노드들과 같은 평면에서 생각해보지 말고, 아래 그림처럼 3차원적으로 생각해서 1번 노드를 분리하고 생각해보면 좀 쉬울 것 같다.

먼저 1) 다들 노드들끼리의 간선에서 장애가 발생한 경우는 고려할 게 없는 게, 디폴트로 모든 노드가 1번 노드와 연결되어 있으므로 애초에 다른 노드들끼리는 아무 간선도 연결되어 있지 않아도 된다. "모든 길은 로마로"라는 말처럼, 모든 길은 일단 1번 노드로 통하기 때문이다. 두 번째로 2) 1번 노드와의 간선에서 장애가 발생한 경우는 1번 노드를 제외한 노드들끼리의 MST가 필요하다. 1번 노드로 가는 길이 막혔으므로 다른 노드들끼리 서로 전부 연결되어 있어야 하는데, 모든 노드를 최소 비용으로 방문하는 문제이므로 딱 MST이다.

3) 다른 노드가 장애가 발생한 경우는 1)이랑 마찬가지로 어쨌던 다른 살아있는 노드들은 1번 노드로 가는 길이 있으므로 서로 연결이 가능하다. 이제 4) 1번 노드가 장애가 발생한 경우가 문제가 되는데, 이것도 3)이랑 마찬가지로 MST 문제가 된다. 다른 노드들끼리 서로 전부 연결되어 있어야 하기 때문이다.

이제 MST 문제라는 것을 알게 되었다. 그런데 2차적으로 마음에 걸렸던 건 "이미 연결되어 있는 간선의 존재"이다. 왠지 모르게 이 간선들을 반드시 포함해서 MST를 만들어야 할 것 같은 착각이 든다. 그리고 간선이 이미 연결되어 있으므로 kruskal로만 풀 수 있을 것 같은 느낌도 든다. 이건 관점을 좀 다르게 하면 해결되는 문제인데, "이미 연결되어 있다=가중치가 0이다"라고 생각하면 그냥 해당 간선들에 대해서 가중치만 0으로 만들어 준 후 MST를 구하면 된다. 따라서 prim으로도 풀 수 있다(아래 풀이가 prim으로 푼 방식).

시간 복잡도로 고민해봐도 n(1 ≤ n ≤ 1,000)이므로, 프림의 경우 (우선순위 큐 구현 시) O(ElogV) = 500,000 * 3이고, 크루스칼의 경우 O(ElogE) ≈ 500,000 * 5이므로 프림으로 구현하는 게 더 빠르다.

올바른 풀이 코드

코너 케이스와 문제의 조건을 잘 잡아내야 한다. 우선 1번 노드는 무조건 다른 모든 노드들과 연결되어 있으므로, 애초에 MST의 고려 대상도 아니다. 따라서 1번 노드는 제외하고 2번 노드부터 MST를 시작한다고 보면 된다. 또한 노드가 하나밖에 없는 경우는 안정적인 네트워크이므로 바로 return해야 한다. 그리고 이미 연결되어 있던 간선(즉, 가중치가 0인 간선)은 새롭게 추가된 간선이 아니므로 정답 노드 쌍에서 제외해야 한다.

#include <climits>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

typedef pair<int, int> ci;       // <w, y>
typedef tuple<int, int, int> tp; //<w, x, y>

void solution(int n, int start, vector<vector<ci>> &graph) {

    // 코너 케이스-노드가 하나밖에 없다면 여기서 리턴
    if (n == 1) {
        cout << 0 << " " << 0 << '\n';
        return;
    }

    vector<bool> visited(n + 1, false);
    vector<int> distance(n + 1, INT_MAX);
    vector<ci> edge(0); // 연결해야 하는 쌍
    priority_queue<tp, vector<tp>, greater<>> pq;

    int x = 0;
    int k = 0;

    distance[start] = 0;
    pq.push(make_tuple(0, start, start));

    while (!pq.empty()) {
        auto [curr_w, curr_x, curr_y] = pq.top();
        pq.pop();

        if (visited[curr_y]) {
            continue;
        }

        visited[curr_y] = true;
        x += curr_w;

        // 원래 추가되어 있던 쌍이라면 count하지 않음
        if (curr_w != 0) {
            k++;
            edge.push_back(make_pair(curr_x, curr_y));
        }

        for (auto [linked_w, linked_n] : graph[curr_y]) {
            if (!visited[linked_n] && linked_w < distance[linked_n]) {
                pq.push(make_tuple(linked_w, curr_y, linked_n));
                distance[linked_n] = linked_w;
            }
        }
    }

    // 코너 케이스-이미 안정적인 네트워크라면
    if (x == 0) {
        cout << 0 << " " << 0 << '\n';
        return;
    }

    // 출력
    cout << x << " " << k << '\n';
    for (int i = 0; i < edge.size(); i++) {
        cout << edge[i].first << " " << edge[i].second << '\n';
    }

    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m; // 컴퓨터 개수 n(1 ≤ n ≤ 1,000), 컴퓨터 쌍의 개수 m(0 ≤ m ≤ 10,000)
    cin >> n >> m;

    // vector<vector<ci>> graph(n + 1, vector<ci>(n + 1, {-1, 0}));
    vector<vector<ci>> graph(n + 1, vector<ci>(0));

    vector<ci> temp(0);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        temp.push_back(make_pair(x, y));
    }

    // 가중치 모두 저장
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            int w;
            cin >> w;
            if (i <= 1 || j <= 1) {
                continue;
            }
            graph[i].push_back(make_pair(w, j));
            graph[j].push_back(make_pair(w, i));
        }
    }

    for (int i = 0; i < temp.size(); i++) {
        // 가중치 0으로 만들어주기
        graph[temp[i].first][temp[i].second - 2] = make_pair(0, temp[i].second);
        graph[temp[i].second][temp[i].first - 2] = make_pair(0, temp[i].first);
    }

    // 어디서 시작해도 되므로, node 2에서 시작한다고 하기
    solution(n, 2, graph);
}

메모리는 18636 KB, 시간은 140 ms가 걸렸다. 나름 선방한 시간복잡도인 것 같다.

배운 점

MST 문제의 조건을 만족하는 경우, 예외적으로 튀는 노드나 간선들을 제외하면 무조건 MST로 해결할 수 있다는 점을 배웠다. 그리고 정답 간선을 출력해야 한다는 조건이 있으면 우선순위 큐에 튜플로 노드와 간선을 모두 저장해야 한다는 점을 알게되었다. 기존에 내가 구현하던 방식은 pair로 간선의 가중치와 도착 노드만 저장하는 방식이라서, 나중에 뜯어고치려니 힘들었다.