[SW Expert Academy] 5360. 모든 섬의 통신 비용

5360. 모든 섬의 통신 비용

SW Expert Academy의 문제들은 보안문제가 있기 때문에 링크로 대체합니다.

클릭시 이동합니다!

어떻게 풀까?

저도 해당문제를 풀지 못해 갓갓분들의 도움을 받았음을 미리 알려드립니다!

우선, 이 문제는 싸이클들을 기준으로 풀어야 한다는 것을 알 수 있습니다! 

싸이클이 생긴다면 이를 끊어줘야하기 때문이죠!

우선, 이 문제의 특징은, 노드 하나에 간선 하나가 꼭 있다는 것이죠!

따라서, 만들어야 하는 그래프의 모습은 항상 이런 모습입니다.

이 모습 만이 바로 모든 섬이 통신을 할 수 있는 상태이죠!

가장 큰 특징은, 모든 노드들이 딱 하나의 in-degree를 가진다는 것이죠!

그렇다면, 일단 정답을 위한 가장 큰 솔루션을 얻을수 있습니다.

in-degree가 1보다 크면 해당 노드로 들어오는 간선을 하나 빼고 모두 끊어줘야한다!

위 내용을 전제로 깔아놓고, 어떻게 풀어갈지에 대해서 풀어가도록 합시다!

위와 같은 상황이 있다고 하겠습니다.

연결에 문제가 있는부분은 딱 한 군데 입니다.

어떻게 끊으면 싸이클을 만들어버릴수 있을까요!?

어짜피 딱 하나의 선만 남겨야 하기 때문에, 자신을 가리키는 간선들 중에서 가장 비용이 높은 선을 남기고 나머지를 삭제하는게 가장 최소 비용으로 모두를 이을 방법이죠!

(그리고 자신을 가리키는 노드를 알기 위해서는, 자신을 가리키는 노드들에 대한 정보를 미리 저장해야 합니다.)

이렇게 2 + 3 + 4 = 9의 비용으로

아래와 같은 싸이클을 만들 수 있습니다!

다만, 이렇게만 처리하면, 문제가 되는 경우가 있습니다. 아래의 그림을 보시죠!

위에서는 7을 남겨야 합니다!

비용은 2 + 3 + 5 = 10이 최소가 될 것입니다!

하지만, 위처럼 잘라버리면, 싸이클이 끊어지지 않기 때문에 결국 노드를 이을 수가 없게되죠.

다시 말하면, 싸이클을 하나 더 끊어줘야 합니다! 

여기서, 싸이클을 끊는 방법은 2 가지가 있습니다.

1. 두 번째로 큰 간선을 끊는다.

2. 첫 번째로 가장 큰 간선을 끊고, 싸이클을 이루는 간선 중에서 하나를 끊는다.

위 그림에서 처럼, 두 번째로 큰 간선을 자르면 2 + 3 + 7 = 12의 비용이 될 것입니다!

그리고, 만약 싸이클 중에서 가장 작은 간선의 비용이 1이라면, 2 + 3 + 5 + 1 = 11의 비용일 것 입니다.

위의 경우에는, 2, 3, 5, 1의 비용을 가지는 간선을 자르는 것이 가장 최소의 비용으로 싸이클을 만들 수 있는 경우일 것 입니다!

만약, 싸이클 중에서 가장 작은 간선의 비용이 5라면, 2 + 3 + 5 + 5 = 15가 될 것입니다.

이렇게 되면, 그냥 7과 2와 3을 자르는 것이 훨씬 더 적은 비용으로 싸이클을 만들 수 있는 비용이 됩니다!

이렇게 위의 두 가지 경우를 모두 확인하면서, 더 적은 비용을 선택하면 싸이클을 만들 수 있습니다!

하지만, 꼬리가 여러개일 경우 조금 복잡해질 수 있습니다!

위의 그림을 통해 설명하겠습니다!

우선, 왼쪽을 처리하겠습니다! 7이 가장 큰 비용이기 때문에, 2, 3, 5의 비용을 가지는 간선들을 제거합니다.

그리고, 오른쪽에 있는 부분은 1의 간선 비용이 더 작기 때문에 1의 연결을 끊습니다!

앗, 아까처럼 제거해도 싸이클이 남아서 연결을 할 수 없습니다!

1개 일때는 비교가 쉬웠지만, 2개 이상일때는 어떻게 비교하는게 좋을까요?

아까 했던 것과 비슷하게 처리하면 됩니다!

이를 해결하기 위해서 '손해값'이라는 개념을 사용하겠습니다!

지금까지는 계속 간선이 최대인 것만 남겼지만,

두 번 째로 비용이 큰 간선을 삭제하는 비용을 구한 후에 이 비용과 처음에 구한 비용의 차이 입니다.

두 비용간의 차이이기 때문에, 만약 처음에 구한 비용에다가 이 '손해값'을 더하면, 결국 두 번째로 큰 간선을 이용해서 싸이클을 만드는 경우의 비용을 구할 수 있습니다!

그림으로 예를 들어드리겠습니다. 

2 번째로 비용이 큰 간선은 5이기 때문에, 해당 간선을 빼고 생기는 비용은 바로 12입니다.

그리고, 처음에 들었던 비용은 2 + 3 + 5 10이죠!

즉, 손해값은 이 두 차이인 2가 됩니다.

그리고, 처음에 2 + 3 + 5 = 10에서 손해값인 2를 더하면, 

싸이클을 자르는데 드는 비용인 2 + 3 + 5 + 7 = 12를 얻을 수 있습니다!

그리고, 어짜피 달라지는 간선은 첫 번째로 비용이 큰 간선이 두 번째로 비용이 큰 간선으로 변하는 것 뿐이기 때문에, 

(위의 경우에는 비용이 2 + 3 + 5에서 2 + 3 + 7로 변화)

첫 번째로 비용이 큰 간선과 두 번쨰로 비용이 큰 간선을 빼 주기만 하면됩니다!

위의 경우에는 7 - 5 = 2 가 되는거죠!

손해값은 다시 말하면, 싸이클을 포함하는 간선을 자르지 않을 때, 싸이클을 포함하도록 간선을 자르도록 수정할 때 드는 비용입니다.

즉, 애초에 싸이클을 자르도록 하는 경우에는 손해값이 0이라는 의미 입니다! 

손해값이 0인 경우는 간단합니다. 제일 큰 비용의 간선이 싸이클에 포함이 안될 때 이죠!

위의 그래프에서, 만약 7의 비용을 가지는 간선의 비용이 3 이었다면, 

제일 비용이 큰 간선은 5이고, 나머지 간선들을 모두 잘라버릴 것입니다!

그러면 자연스럽게 싸이클의 간선도 잘리기 때문에, 굳이 싸이클을 자르기 위해 손해를 가질 필요가 없는 것이죠.

싸이클에 포함이 되는지, 안되는지 알아보는건 쉽습니다. 위상 정렬로 in-degree를 정리해 놓았기 때문이죠.

해당 간선이 시작하는 노드의 in-degree가 1이라면, 해당 간선은 싸이클을 이루는 간선 이라고 할 수 있습니다!!

굳이 싸이클의 간선을 자르기 위해 손해값을 증가시킬 필요가 없다!

이제 오른쪽의 경우를 봅시다!

오른쪽의 경우에는 어짜피 간선이 2개이므로, 손해값은 5가 되겠군요!

그럼 이렇게, 손해값들 2개를 구했습니다.

바로, 2와 5이죠!

어짜피, 안에있는 싸이클은 딱 한번만 끊어지면 하나의 싸이클로 이을 수 있습니다!

굳이 7과 6을 동시에 끊을 필요가 없다는 것이죠! 둘 중에 손해가 작은 것 하나만 끊으면 됩니다.

따라서, 손해의 비용이 작은 2를 더해서, 아래처럼 간선을 잘라서 싸이클을 만들 수 있고, 이것이 바로 최소의 비용으로 싸이클을 만드는 방법입니다.

비용은 2 + 3 + 7 + 1 = 13 입니다!

다만, 아래와 같은 경우엔 다릅니다!

달라진 부분은 싸이클에서 비용이 1인 간선이 생겼다는 것입니다!

이렇게 보면, 손해 값이 2와 5인것 뿐만이 아니라, 비용 1의 싸이클을 끊어서 노드들을 이어버릴 수 있습니다!

즉, 2+ 3 + 5+ + 1 + 1의 비용으로 모든 노드들을 이어버릴 수 있다는 것입니다!!!!!!

즉, 전체의 손해값은 in-degree가 1이 넘는 노드들에서의 손해값과, 싸이클을 이루는 간선들 중 최소의 비용을 가지는 간선 중에서 가장 최솟값이 되겠죠!!

그리고, 만약 싸이클을 이미 지울수 있는 경우에는 손해값이 어짜피 0이기 때문에, 위 연산을 해도 손해값은 가장 작은 0이라는 값을 가질 것입니다.

그럼 이제 방법을 정리해봅시다.

1.  위상 정렬을 통해 in-degree가 1이 되는 싸이클들을 찾는다.

2. in-degree가 1이 되는 노드 중에서 자신을 가리키는 노드 개수가 2개 이상인 노드를 찾는다.

3. 해당 노드에서의 '손해값'과 싸이클로 변하기 위한 비용을 구한다.

4. 모든 노드들에대해 3번을 반복한다. 손해값은 계속 작은 값으로 갱신한다.

5. 이제, 손해값과 싸이클을 이루는 간선들 중 비용이 가장 작은 값을 비교해서 작은 값을 결과값에 더해준다.

이렇게 되겠군요!

하지만, 이는 딱 하나의 싸이클에 대해서만 끝난 것입니다!

아래의 그림 처럼 이렇게 만들어진 싸이클들이 여러개 이루어져 있을수도 있죠!

따라서, 싸이클마다 번호를 매긴 다음에 싸이클 별로 결과값들을 따로 구해서 마지막에 종합적으로 더해주는 방법이 필요합니다!

이를 위해서 유니온 파인드를 이용합시다!

 

이 외에도 한 번 생각해 봐야할 부분이 있습니다.

지금까지 생각했던 것은 싸이클과 직접 연결된 꼬리에 대해서였지만, 아래처럼 싸이클과 전혀 상관없는 꼬리들도 있습니다.

위상 정렬을 이용해서 꼬리를 제거하면 이러한 꼬리들은 처리되지 않죠.

그렇다면, 위 상황에서 가장 비용이 적게 in-order를 1로 만들어 버리는 방법은 무엇일까요?

바로, 가장 가중치가 많은 선을 빼고 나머지를 다 끊어버리는 것이죠! 

싸이클보다 굉장히 처리하기가 쉽습니다.

이렇게 연결하면 320의 비용이 들 것입니다. 싸이클에서와 달리 탈도 없죠.

위상 정렬로 사라진 꼬리인지 알아내는 것은 쉽습니다!

처음 입력 받으면서 만들어준  in-degree와, 위상 정렬 후의 in-degree값을 비교하면 됩니다.

처음에는 in-degree가 1보다 컸는데, 위상 정렬 후에 in-degree가 0이 됬다면, 자신을 가리키는 간선들의 값 중에서 가장 큰 값을 빼고 모두 결과값에 더해주는 작업을 해 줍시다!

그리고! 설명을 안드린 아주 예외적인 상황이 하나 있습니다!

바로, 처음부터 싸이클인 경우입니다.

제가 지금까지 제안한 방법에 의하면, 처음부터 싸이클인 경우에 손해값으로 자신의 싸이클 중에서 가장 작은 값을 가지는 간선의 비용을 더해주는 결과를 불러옵니다!

따라서, 처음부터 싸이클이었고, 싸이클의 개수가 1 개였으면 손해값을 더해주지 않는 작업을 따로 해줍시다!

이렇게 하면 Pass를 받을 수 있습니다!!

코드

//https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVWj7S6sXUDFAUO&categoryId=AWVWj7S6sXUDFAUO&categoryType=CODE&&&
// 5360. 모든 섬의 통신 비용
#pragma once
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
 
int que[100001], f, r;
int indeg[100001];
vector<int> child[100001];
int info[100001][2];
int indeg2[100001];
vector<int> adj[100001];
int g[100001];
int p[100001];
 
int find(int idx) {
    int pa = p[idx];
    if (pa > 0) return p[idx] = find(pa);
    return idx;
}
 
void join(int a, int b) {
    int pa = find(a);
    int pb = find(b);
 
    if (pa == pb) return;
 
    if (p[pa] > p[pb]) {
        int temp = pa;
        pa = pb;
        pb = temp;
    }
 
    p[pa] += p[pb];
    p[pb] = pa;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
    
    for (int tc = 1; tc <= t; tc++) {
        int n;
        scanf("%d\n", &n);
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
            p[i] = -1;
            indeg[i] = 0;
            child[i].clear();
            g[i] = 0;
        }
 
        f = r = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d %d\n", &info[i][0], &info[i][1]);
            indeg[info[i][0]]++;
            join(i, info[i][0]);
            child[info[i][0]].push_back(i);
        }
 
        memcpy(indeg2, indeg, sizeof(indeg));
 
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0) {
                que[r++] = i;
            }
        }
 
        while (f != r) {
            int now = que[f++];
            int next = info[now][0];
 
            indeg[next]--;
            
            if (indeg[next] == 0) {
                que[r++] = next;
            }
        }
        
        int gNum = 1;
        for (int i = 1; i <= n; i++) {
            if (indeg[i]) {
                if (g[find(i)] == 0) g[find(i)] = gNum++;
                adj[g[find(i)]].push_back(i);
            }
        }
 
        long long res = 0;
 
        for (int i = 1; i <= n; i++) {
            long long max = 0, temp = 0;
            if (indeg[i] == 0 && indeg2[i] > 1) {
                for (int j = 0; j < child[i].size(); j++) {
                    temp += info[child[i][j]][1];
                    max = max < info[child[i][j]][1] ? info[child[i][j]][1] : max;
                }
                temp -= max;
                res += temp;
            }
        }
 
        long long mi = 0x7fffffffffffffff;
        bool cycle = true;
 
        for (int i = 1; i < gNum; i++) {
            long long temp = 0;
            mi = 0x7fffffffffffffff;
 
            for (int j = 0; j < adj[i].size(); j++) {
                int now = adj[i][j];
 
                if (child[now].size() > 1) {
                    temp = 0;
                    cycle = false;
 
                    long long max = 0;
                    long long max2 = 0;
                    int midx = 0;
                    for (int k = 0; k < child[now].size(); k++) {
                        if (max < info[child[now][k]][1]) {
                            max2 = max;
                            max = info[child[now][k]][1];
                            midx = child[now][k];
                        }
                        else if (max2 < info[child[now][k]][1]) {
                            max2 = info[child[now][k]][1];
                        }
                        temp += info[child[now][k]][1];
                    }
 
                    temp -= max;
                    if (indeg[midx]) {
                            mi = mi > max - max2 ? max - max2 : mi;
                    }
                    else mi = 0;
                    res += temp;
                }
            }
 
            for (int j = 0; j < adj[i].size(); j++) {
                mi = mi > info[adj[i][j]][1] ? info[adj[i][j]][1] : mi;
            }
 
            res += mi;
        }
        res -= cycle && (gNum == 2) ? mi : 0;
        printf("#%d %lld\n", tc, res);
    }
    return 0;
}

으아.. 코드도 깁니다.

여담

시간 복잡도 계산이 정말 어려운 것 같습니다.

하지만, 단계를 해결하면서 같은 노드를 두 번 방문하는 일은 없습니다. 따라서, O(N)의 시간복잡도를 가진다고 할 수 있습니다!