[백준] 1647번 : 도시 분할 계획

문제

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

풀이

[백준] 1647번 : 도시 분할 계획 🥇(골드 4)
🎯 48.708%
⏰ 걸린 시간 : 28분
⏲ 시간복잡도
: 프림 O(ElogV) :
V인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

• 알고리즘 유형 : MST (최소 스패닝 트리)[프림(Prim)]

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

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

📚 [Prim]

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

코드(code)

import sys
import heapq
input = sys.stdin.readline

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

for _ 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))
    node_lengths=[]
  
    while q:
        len, node = heapq.heappop(q) # heapq특성상 가중치를 기준으로 정렬 하므로 이렇게 뽑는다.
        if visited[node] == 0:
            visited[node] = 1
            node_lengths.append(len)
            for next_len, next_node in graph[node]:
                heapq.heappush(q,(next_len,next_node))

    return sum(node_lengths) -max(node_lengths)

print(prim())

프림과 다익스트라 차이 ?

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

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

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

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

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

회고

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

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/MST/1647(%EB%8F%84%EC%8B%9C%20%EB%B6%84%ED%95%A0%20%EA%B3%84%ED%9A%8D).py