[Python] 1922 - 네크워트 연결 - 트리 구조, 가장 적은 비용, 최소 스패닝 트리

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

1922번: 네트워크 연결

 

from sys import stdin
 
N = int(stdin.readline())
M = int(stdin.readline())
 
def find_parent(a):
    if parent[a] != a:
        parent[a] = find_parent(parent[a])
    return parent[a]
 
 
def union(a, b):
    p_a, p_b  = find_parent(a), find_parent(b)
    if p_a < p_b:
        parent[p_b] = p_a
    else:
        parent[p_a] = p_b
 
link = []
parent = [i for i in range(N)]
cost_re = 0 #Cost of result
 
for i in range(M):
    c_a, c_b,c_cost = map(int, stdin.readline().split())
    link.append([c_a-1, c_b-1, c_cost])
 
link.sort(key=lambda x : x[2])
 
for edge in link:
    a, b, cost = edge[0], edge[1], edge[2]
 
    if find_parent(a) != find_parent(b): #부모 노드가 다르면
        union(a, b) #에지를 이어준다.
        cost_re += cost
 
print(cost_re)

[풀이]

도저히 JAVA로는 머리가 안돌아가서 Python을 사용하였다..... ㅠ-ㅜ 

(compare 함수 overloading하다가 포기함)... sort(lamda) 짱..

 

먼저 각 노드별로 부모노드를 찾아야한다. 근데 일단 자기 자신이라고 치고 짱박아둔다.

 

먼저 연결된 노드들과 비용들을 연결되었음을 나타내는 리스트인 link에 추가해준다.

이 리스트를 최소비용으로 연결해야 하므로 cost를 기준으로 정렬을 한다.

정렬한 애들을 하나하나 훑는다.

이 때 부모 노드가 다른지를 확인해줘야한다. 부모 노드가 같을 경우는 연결했을 때 circle이 생긴다. 그럼 안된다.

따라서  부모 노드가 다를 경우, 에지를 이어준다. 에지를 이어주고 cost를 더해준다!!

끝~

 

프림	크루스칼
정점 위주의 알고리즘	간선 위주의 알고리즘
시작점을 정한다. 시작점에서 가까운 정점을 선택하면서 트리 구성 Cycle이 생기지 않음.	시작점을 따로 정하지 않는다. 최소 비용의 에지를을 차례로 union하며 트리를 구성 Cycle 확인 필수.
간선의 개수가 많은 경우	간선의 개수가 작은 경우
	정렬하느라 오래걸림

 

크루스칼 알고리즘 (Kruskal Algorithm)

• 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

• 최소 스패닝 트리 : 선택한 간선의 가중치의 합이 최소인 스패닝 트리

[과정]

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 1-3 반복

프림 알고리즘 (Prim Algorithm)

• 정점 선택을 기반으로 하는 알고리즘

[과정]

1. 임의의 간선 선택

2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택. cycle이 만들어지는 경우를 제외한다.

3. 1-2 반복