![프림 알고리즘(최소신장트리, MST, prime)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbQO2gF%2FbtsvkpQioKT%2FGKkVKNRxDNNKwlfF5ZMPz1%2Fimg.png)
![leejinwoo1126](https://t1.daumcdn.net/tistory_admin/static/manage/images/r3/default_L.png)
목차
최소 신장 트리 (MST, Minimum Spanning Tree)
그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리
MST 특징
1) 간선(Edge)의 가중치 합이 최소
2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)
3) Cycle을 포함하면 안된다
프림(Prime) 알고리즘
- 인접 리스트와 우선 순위 큐, 그리고 방문 배열을 사용
- 시작점을 기준으로 인접한 정점 중에 아직 연결하지 않았고, 가중치가 최소인 정점을 선택 반복하여 노드를 연결함
- 우선 순위 큐를 집합으로 보고, 가장 가중치가 작은 노드를 우선 순위로 하여 연결(=방문) 여부 확인 후 연결 처리 한다.
- 시간 복잡도 : O((V + E)logV) = O(ElogV)
- 우선 순위 큐에서 최소 힙으로 정렬하기 때문에 logV^2 만큼의 시간이 소비됨 (=최대 간선의 개수는 정점 제곱 이하)
2logV 에서 상수 생략 되어 logV 남음
- 인접리스트 그래프 순회는 O(V + E)만큼 소요
절차
1) 간선의 정보를 인접 리스트로 나타냄 (양방향 그래프로 표현)
2) 프림 알고리즘 수행
2-1) 시작 노드에 대한 정보를 PriorityQueue에 추가 (최소힙, 간선 가중치 기준 오름차순 정렬)
2-2) 연결 여부 확인
이미 연결된 경우 - continue
연결되지 않은 경우 - 방문처리 후, 비용 합산, 연결 노드 조회
3) 해당 노드에 연결된 노드 중에 아직 방문하지 않은 경우 우선 순위 큐에 추가
4) 2~3번까지 과정 반복하며 사이클 형성되지 않는 MST 최소 비용 구함
참고. 크루스칼 알고리즘 (사용하는 자료 구조 잘 구분하기)
크루스칼 알고리즘 (MST, 최소 신장 트리, kruskal)
목차 최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리 MST 특징 1) 간선(Edge)의 가중치 합이 최소 2) N개의 정점을 가지는
dev-ljw1126.tistory.com
프림 알고리즘 예시
1) 초기화 , A 노드 시작
- 양방향 그래프로 생각하고 인접 리스트 초기화
- 시작 노드를 A로 해서 PriorityQueue에 추가
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 0 )
- A노드에 연결된 노드 중 아직 방문하지 않은 노드 D, B 정보를 PriorityQueue에 추가
2) D 노드
- PriorityQueue에서 비용이 가장 작은 D노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 0 + 5 = 5 )
- D노드에 연결된 노드 중 아직 방문하지 않은 노드 B, E, F 정보를 PriorityQueue에 추가
A노드의 경우 시작노드로 이미 방문 처리 되었기 때문에 추가되지 않음
3) F 노드
- PriorityQueue에서 비용이 가장 작은 F노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 5 + 6 = 11 )
- F노드에 연결된 노드 중 아직 방문하지 않은 노드 E, G 정보를 PriorityQueue에 추가
4) B 노드
- PriorityQueue에서 비용이 가장 작은 B노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 11 + 7 = 18 )
- B노드에 연결된 노드 중 아직 방문하지 않은 노드 C, D, E 정보를 PriorityQueue에 추가
5) E 노드
- PriorityQueue에서 비용이 가장 작은 E노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 18 + 7 = 25 )
- E노드에 연결된 노드 중 아직 방문하지 않은 노드 C, G 정보를 PriorityQueue에 추가
6) C 노드
- PriorityQueue에서 비용이 가장 작은 C노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 25 + 5 = 30 )
- C노드에 연결된 노드 중 아직 방문하지 않은 노드 없으므로 PriorityQueue에 추가 정보 없음
7) 이미 방문한 E, C, B continue 처리
- 앞서 최소 비용으로 E, C, B노드를 방문 처리함 (= 가치가 없다)
- 순차적으로 PriorityQueue에서 꺼낸 후 방문 여부 확인 조건문 통해 continue 처리
8) G 노드
- PriorityQueue에서 비용이 가장 작은 G노드 정보를 꺼냄
- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 30 + 9 = 39 )
- G노드에 연결된 노드 중 아직 방문하지 않은 노드 없으므로 PriorityQueue에 추가 정보 없음
- PriorityQueue에 남은 나머지 정보도 마찬가지로 이미 방문 처리 되어 있어서, continue 처리됨
- 총 39 비용으로 MST 형성
백준 추천 문제
풀이 참고
https://dev-ljw1126.tistory.com/365
[BOJ1414] 불우이웃돕기 (프림, 최소 신장트리, 그리디)
문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터
dev-ljw1126.tistory.com
https://dev-ljw1126.tistory.com/366
[BOJ4386] 별자리 만들기 (프림 알고리즘, 최소신장트리, MST)
문제 링크 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건
dev-ljw1126.tistory.com
https://dev-ljw1126.tistory.com/367
[BOJ1368] 물대기 (프림 알고리즘, 최소 신장 트리, 그리디)
문제 링크 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다
dev-ljw1126.tistory.com
'알고리즘 > 탐욕(그리디)' 카테고리의 다른 글
[BOJ1339] 단어 수학 (Java, 그리디, 완전 탐색) (0) | 2025.01.20 |
---|---|
[BOJ21925] 짝수 팰린드롬(그리디, 탐욕 알고리즘) (0) | 2023.10.06 |
크루스칼 알고리즘 (MST, 최소 신장 트리, kruskal) (0) | 2023.09.23 |
[BOJ2887] 행성 터널(최소신장트리,MST, 크루스칼 알고리즘) (0) | 2023.09.22 |
[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) (0) | 2023.09.07 |
![leejinwoo1126](https://t1.daumcdn.net/tistory_admin/static/manage/images/r3/default_L.png)
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!