[백준] 16398 행성 연결

문제

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0) 로 주어진다.

출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
parent = [i for i in range(n)]      # 부모 노드 기록

# 연결된 부모 노드 찾기 (with 재귀)
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a
 
# 행렬에서 관리 비용 입력 받기
edges = []       
for i in range(n):
    costs = list(map(int, input().split()))
    for j in range(i+1, n):              # 양방향 그래프이므로 절반만 저장 (i < j인 경우만 간선 추가)
        edges.append((costs[j], i, j))     # (비용, 노드 1, 노드 2)
        
edges.sort()   # 가장 저렴한 간선부터 선택하기 위해 비용으로 오름차순 정렬

result = 0
for cost, a, b in edges:
    if find(a) != find(b):
        union(a, b)
        result += cost
        
print(result)

시간 복잡도 → $O(E \,log \,E)$ ( $E$ = 간선의 수)
edges.sort()에서 간선을 정렬할 때, $O(E\, log \,E)$ 만큼의 시간이 소요
그리고 union find 연산은 $O(\alpha(N))$ 만큼의 시간이 소요되는데, $\alpha(N)$ 는 아커만 함수의 역함수라는 것으로 거의 상수에 가까울 정도로 매우 느리게 증가하는 함수라고 한다. 이를 간선의 개수만큼 반복하므로 $O(E\, \alpha(N))$ ~ $O(E)$ 만큼의 시간이 걸린다. 그래서 위 코드의 총 시간 복잡도는 $O(E\, log \,E)$
공간 복잡도 → $O(N+E)$
edges : $E$ 개의 간선 → $O(E)$
parent : $N$ 개의 노드 → $O(N)$

코멘트

이 문제는 크루스칼 알고리즘(Kruskal algorithm)을 이용해서 푸는 문제이다. 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree; MST)를 찾는 알고리즘 중의 하나이다. 최소 신장 트리는 그래프의 모든 정점을 포함하면서 사이클이 없고, 그 중에서도 간선 가중치 합이 최소인 트리를 말한다. 행성 연결 문제도 행성들을 모두 연결하면서 비용의 합이 최소가 되어야 하므로 크루스칼 알고리즘을 이용하는 것이 적절하다.

크루스칼 알고리즘은
1) 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬하고,
2) 가중치가 낮은 간선부터 하나씩 선택하고,
3) 선택한 간선이 사이클을 만들지 않으면 최소 신장 트리에 포함시킨다. 이 때, 사이클이 있는지 여부를 union find 알고리즘으로 체크한다.
* union find 알고리즘은 집합을 효율적으로 나누고 합치기 위한 알고리즘이다. 각 노드의 부모 노드를 찾아서(find) 연결 관계를 찾고, 사이클이 아니라면 합친다(union)
4) 최소 신장 트리의 간선 개수가 (노드 개수 - 1)개가 되면 알고리즘을 종료한다.

References

https://www.acmicpc.net/problem/16398

[알고리즘] 유니온 파인드 (Union-Find)

두 노드는 서로 같은 집합에 속할까?

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find

[알고리즘] Union-Find Algorithm (유니온 파인드 알고리즘)

유니온 파인드 알고리즘이란? 💡유니온 파인드 알고리즘: 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 왜 이름이 유니온 파인드인가? 유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다. Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다. Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다. 크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다. 유니..

https://memodayoungee.tistory.com/106