파이썬 백준 16398번 : 행성 연결 - MST, 프림 알고리즘

문제

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

 

 

🌍풀이

최소 신장 트리 문제이다. 프림 알고리즘으로 해결했다.

 

import sys
def Prim():
    dist=[1000000000]*N
    dist[0]=0 #탐색을 시작할 index(아무거나 상관없음)
    for i in range(N):
        min_cost = 1000000000
        min_j = -1
        for j in range(N): #dist배열의 가장 작은값 찾아서 그로 이동
            if j not in visited and dist[j]<min_cost:
                min_cost=dist[j] #값 갱신
                min_j=j
        visited.add(min_j) #방문 표시

        for k in range(N): #min_j로 이동해서 더 짧은 거리가 있는지 확인 후 갱신
            if k not in visited and Graph[min_j][k]<dist[k]:
                dist[k]=Graph[min_j][k]
    return sum(dist)

N=int(sys.stdin.readline())
Graph=[]
visited=set()
for i in range(N):
    temp=list(map(int,sys.stdin.readline().strip().split()))
    Graph.append(temp)
print(Prim())

 

---

프림 알고리즘

프림 알고리즘은 그리디 기법으로, 현재 상황에서의 최선을 선택하다 보면 전체의 최선이 되는 것이 기본이다.

그래프와 간선의 정보를 표현하고, 각 노드까지의 최단 거리 도달을 나타내는 dist 배열을 모두 무한대로 초기화한후 시작한다

 

 

 

첫번째로 0노드를 선택하자(어디서 시작하든 상관없다.)

0번은 방문체크한다.

0번 노드를 기준으로 1,2,3,4의 dist값을 업데이트한다.

이중 최소인 3번 노드로 이동한다.

 

 

 

 

 

두번째로 노드 3에서 최단 경로를 업데이트한다.

3을 방문체크한다. 

이미 방문된 0을 제외하고 1,2,4번노드의 dist를 업데이트한다.

이경우 이미 dist가 최적화 되어있어 업데이트가 이루어지지 않는다.

3과 연결되고 이미 방문하지 않은 노드들중 간선의 가중치가 가장 작은 4로 이동한다. 

 

 

 

 

세번째로 노드4에서 최단경로를 업데이트한다.

4를 방문체크한다.

이미 방문된 0,3을 제외하고 1,2의 dist가 업데이트 된다.

더 작은 노드 1로 이동한다. 

 

 

 

 

마지막으로 1로 이동해서 방문체크하고 방문되지 않은 2의 dist를 업데이트한다. 현재는 5가 4보다 크기 때문에 업데이트 되지 않는다.

 

 

 

 

 

 

 

이후 2가 방문 처리되면 모든 노드를 최적화 했으므로 종료된다. 

결과는 dist배열의 합이다.