최소 신장 트리를 구하는 프림 알고리즘, 크루스칼 알고리즘 재활하기1

1. 문제

 

16398번: 행성 연결 (acmicpc.net)

16398번: 행성 연결

 

2. 풀이

 

최소 신장 트리의 비용을 구하는 알고리즘은 기본이 프림 알고리즘이랑 크루스칼 알고리즘

 

크루스칼 알고리즘이 간단해서 기억이 잘 난다..

 

1) (가중치, 간선) 형태로 edges에 넣어 가중치 기준으로 오름차순 정렬하고

 

2) 가중치가 적은 간선부터 순회하여 정점 a와 정점 b가 서로 parent가 다르다면, union 시키고

 

해당 간선을 선택하고 간선의 가중치를 더해간다.

 

3) parent가 같다면 해당 간선은 선택하지 않는다

 

4) 총 v-1개 선택하면.. 알고리즘을 멈추고, 그동안 누적한 가중치 합이 최소 신장 트리의 비용이다.

 

from sys import stdin

def find_parent(x,parent):
    
    if x != parent[x]:
        
        parent[x] = find_parent(parent[x],parent)
    
    return parent[x]

def union(a,b):
    
    a = find_parent(a,parent)
    b = find_parent(b,parent)

    if parent[a] < parent[b]:
        
        parent[a] = b
    
    else:
        
        parent[b] = a

n = int(stdin.readline())

C = [list(map(int,stdin.readline().split())) for _ in range(n)]

parent = [i for i in range(n+1)]

edges = []

for i in range(n):
    
    for j in range(n):
        
        if i != j:
            
            edges.append((C[i][j],i,j))

edges.sort()

answer = 0

select = 0

for c,a,b in edges:
    
    if find_parent(a,parent) != find_parent(b,parent):
        
        union(a,b)
        answer += c
        select += 1
    
    if select == n-1:
        
        break

print(answer)

 

근데 문제가 인접행렬로 그래프가 주어졌는데.. 인접행렬로 주어진 경우 크루스칼 알고리즘은 적절하지 않다

 

(비용, 정점1,정점2)를 가지는 리스트 형태로 바꿔야하니까

 

바꿔서 크루스칼 알고리즘을 쓸수도 있는데 바꾸는데 $O(N^{2})$이다 보니 시간 비용이 만만치 않다

 

억지로 프림 알고리즘 안쓸려고 했는데..

 

그래도 정말 기본이니까 복기한다는 차원에서...

 

최소 신장 트리를 찾는 두번째 알고리즘 - 프림 알고리즘 파헤치기 - (tistory.com)

최소 신장 트리를 찾는 두번째 알고리즘 - 프림 알고리즘 파헤치기 -

 

-----------------------------------------------------------------------------------------------------------------------------

 

1) 임의의 정점을 하나 선택해서 최초 최소 신장 트리를 구성함

 

임의의 정점 번호 r과 마지막 정점 번호 v에 대하여..

 

mst = [0]*v와 weights = [INF]*v로 초기화

 

mst는 각 정점이 최소 신장 트리에 포함되었느냐? 아니냐?

 

weights는 각 정점이 최소 신장 트리에 포함되었을때, 드는 비용

 

시작 정점 r에 대하여.. weights[r] = 0으로 시작

 

mst[r] = 1으로 시작하지는 않는다.. 반복문을 돌면서 자연스럽게 mst[r] = 1이 될거거든

 

from sys import stdin

INF = 1000000000000000000000

def prim(r,v):

    mst = [0]*v

    weights = [INF]*v

    #mst[r] = 1
    weights[r] = 0

 

 

2) 트리에 포함된 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택

 

mst에 아직 포함되어 있지 않고, 가중치 weights[i]가 최소인 정점 i를 먼저 찾는다.

 

그러한 정점 i를 최소 신장 트리에 포함시킨 다음, (mst[r] = 0으로 시작하기 때문에, 최초 r이 먼저 선택됨)

 

최소 신장 트리에 포함되어 있지 않으면서,(mst[w] == 0) 해당 정점과 인접한 정점(C[u][w] > 0)에 대하여...

 

w의 비용 weights[w]를 최솟값으로 갱신시킨다

 

 

3) 모든 정점이 선택될때까지 반복

 

이를 v-1번 반복하면.. weights의 합이 최소신장트리의 비용이 된다

 

 

from sys import stdin

INF = 1000000000000000000000

def prim(r,v):

    mst = [0]*v

    weights = [INF]*v

    #mst[r] = 1
    weights[r] = 0

    for _ in range(v-1):
        
        u = 0
        w = INF

        for i in range(v):
            
            if mst[i] == 0 and weights[i] < w:
                
                w = weights[i]
                u = i
        
        mst[u] = 1

        for w in range(v):
            
            if mst[w] == 0 and C[u][w] > 0:
                
                weights[w] = min(C[u][w],weights[w])
    
    return sum(weights)

n = int(stdin.readline())

C = [list(map(int,stdin.readline().split())) for _ in range(n)]

print(prim(0,n))

 

 

크루스칼만 쓰지 말고 인접행렬이 주어질때 자신있게 프림 알고리즘으로..