프림 알고리즘(Prim Algorithm) - 구현과 예제

프림 알고리즘(Prim Algorithm) - 구현과 예제

프림 알고리즘 구현

프림 알고리즘에 관한 개요는 이전 포스팅을 참고 바랍니다.

2021.09.25 - [CS/알고리즘] - 프림 알고리즘(Prim Algorithm)

프림 알고리즘은 자료구조에 따라 성능이 차이가 납니다. 여기서는 이진 힙(우선 순위 큐)를 사용하여 구현하겠습니다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Prim { public static class Vertex implements Comparable{ int no; int cost; public Vertex(int no, int cost) { this.no = no; this.cost = cost; } @Override public int compareTo(Vertex o) { return Integer.compare(this.cost, o.cost); } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(in.readLine()); int[][] adjMatrix = new int[N][N]; boolean[] visited = new boolean[N]; int[] minEdge = new int[N]; StringTokenizer st = null; for(int i=0;i pq = new PriorityQueue<>(); // 0번 노드부터 시작 pq.offer(new Vertex(0,0)); while(!pq.isEmpty()) { // 인접한 노드 중 가장 cost가 적은 노드를 꺼냄 Vertex minVertex = pq.poll(); // 그 노드가 이미 방문한 노드면 pass if(visited[minVertex.no]) continue; // 거리 갱신 result += minVertex.cost; // 방문 배열에 체크 visited[minVertex.no] = true; // 모든 노드를 방문했으면 종료 if(++cnt == N) break; //선택된 정점 기준으로 신장트리에 연결되지 않은 타 정점과의 간선 비용 최소로 업데이트 for(int i=0;i adjMatrix[minVertex.no][i]) { minEdge[i] = adjMatrix[minVertex.no][i]; // 큐에 삽입 pq.offer(new Vertex(i,minEdge[i])); } } } System.out.println(result); } }

이진 힙이 cost에 따라 정렬을 수행해야 하므로 Vertex라는 클래스에 Comparable 인터페이스를 implements 하였습니다.

이를 이용한 예제 하나를 풀어보겠습니다.

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

import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; import java.io.BufferedReader; public class 백준1647 { public static class Vertex implements Comparable{ int no; int cost; public Vertex(int no,int cost) { this.no = no; this.cost = cost; } @Override public int compareTo(Vertex o) { return Integer.compare(this.cost, o.cost); } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); ArrayList[] adjList = new ArrayList[n+1]; for(int i=1;i<=n;i++) { adjList[i] = new ArrayList<>(); } int[] minEdge = new int[n+1]; boolean[] visited = new boolean[n+1]; for(int i=0;i pq = new PriorityQueue<>(); pq.offer(new Vertex(1,0)); int max = -1; int result = 0; int cnt = 0; while(!pq.isEmpty()) { Vertex minVertex = pq.poll(); if(visited[minVertex.no]) continue; visited[minVertex.no] = true; result += minVertex.cost; if(maxv.cost) { minEdge[v.no] = v.cost; pq.offer(new Vertex(v.no,v.cost)); } } // // for(int i=1;i<=n;i++) { // if(!visited[i] && adjMatrix[minVertex.no][i] != 0 && minEdge[i]>adjMatrix[minVertex.no][i]) { // minEdge[i] = adjMatrix[minVertex.no][i]; // pq.offer(new Vertex(i,adjMatrix[minVertex.no][i])); // } // } } System.out.println(result-max); } }

프림으로 최소 신장 트리를 구한 후 연결된 간선 중 가장 긴 간선을 빼주면 되는 문제이다. 여기서 주의 할 점은 인접행렬로 구현할 경우 메모리초과가 난다는 점이다. 그래서 인접행렬이 아닌 인접리스트로 풀어주었다.

프림의 구현에는 인접행렬로 구현하였고 이 문제는 인접리스트로 구현했으니 둘 다 공부해보는 것을 추천한다.

from http://dabonee.tistory.com/42 by ccl(A) rewrite - 2021-09-26 01:26:38