[백준] 1197번 : 최소 스패닝 트리

문제

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

풀이

[백준] 1197번 : 최소 스패닝 트리 🥇(골드 4)
🎯 40.932%
⏰ 걸린 시간 : 55분
⏲ 시간복잡도
: 프림 O(ElogV) :
V인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

• 알고리즘 유형 : [프림(Prim)]

✅ 풀이방법 & 최소 스패닝 트리(MST) 알고리즘로 푼 이유?

0. 모든 정점이 다연결 되어 있고, 사이클이 없다, 가중치 합의 최소를 구하라 ➞ MST
1. Kruskal알고리즘은 간선들을 정렬해야하기 때문에 간선이 적으면 Kruskal, 많으면 Prim을 선택한다.

📚 [Prim]

0. 임의의 정점을 선택
1. 해당 정점에서 갈 수 있는 간선을 minheap에 넣는다.
2. 최소값을 뽑아 해당 정점을 방문 안했다면 선택한다.
   비슷한 알고리즘으로 다익스트라 알고리즘이 있다.
   🍯 다익스트라는 전체 요소를 연결하는 것이 아닌 한 정점에서 다른 정점으로 가는 가장 짧은 방법을 구할 때 사용한다.

코드(code)

import sys
import heapq
input=sys.stdin.readline

V, E = map(int,input().split())

graph =[[] for _ in range(V+1)]
visited=[0 for _ in range(V+1)]


for i in range(E):
    A,B,C = map(int,input().split())
    graph[A].append((C,B))
    graph[B].append((C,A))

def prim():
    q = []
    answer,cnt = 0, 0
    q.append((0,1)) # heapq특성상 가중치를 기준으로 정렬 하므로 이렇게 넣어준다.
    while q:
        if cnt == V:
            break

        len, node = heapq.heappop(q) # heapq특성상 가중치를 기준으로 정렬 하므로 이렇게 뽑는다.
        if visited[node] == 0:
            visited[node] = 1
            answer += len
            cnt+=1
            for next_len, next_node in graph[node]:
                heapq.heappush(q, (next_len,next_node))
    return print(answer)
prim()

프림과 다익스트라 차이 ?

1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다.

   • 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다.

2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다.

3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다.

   ➞ 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다.

회고

MST 처음 푼건데 풀면서 늘 것 같다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/MST/1197(%EC%B5%9C%EC%86%8C%20%EC%8A%A4%ED%8C%A8%EB%8B%9D%20%ED%8A%B8%EB%A6%AC).py