[백준] 1922번 : 네트워크 연결

문제

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

풀이

[백준] 1197번 : 최소 스패닝 트리 🥇(골드 4)
🎯 63.183%
⏰ 걸린 시간 : 10분
⏲ 시간복잡도
: 프림 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

N = int(input())
M = int(input())
graph=[[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]

for i in range(M):
    a,b,c = map(int,input().split())
    graph[a].append((c,b)) # heapq특성상 가중치를 기준으로 정렬 하므로 이렇게 넣어준다.
    graph[b].append((c,a))

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

print(prim())

프림과 다익스트라 차이 ?

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

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

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

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

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

회고

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

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/MST/1922(%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20%EC%97%B0%EA%B2%B0).py