[JAVA] 프림 알고리즘 (+ 크루스칼과는 어떻게 다를까?)

이전 포스팅에 이어 이번에는 MST 알고리즘을 구현하는 방식 중 하나인 프림 알고리즘에 대해 알아보려 합니다.

우선 MST에 대해 다시 한번 짚고 넘어가겠습니다.

 

📑 MST

MST를 다시한번 간단하게 설명하면 "최소 비용으로 모든 정점을 연결한 트리 구조"입니다.

MST도 트리이기 때문에, 트리 구조 특성 상 사이클이 발생하면 안되는데요.

이유는 트리는 정점 간 유일한 경로, 최소 연결성이라는 특성이 있기 때문입니다.

 

이러한 MST를 구하는 방식 중 하나인 크루스칼 알고리즘에 대해서는 아래 포스팅을 참고해주세요.

[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)

[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)

 

🏹 Focus On

이번 포스팅의 주요 목적은 이러한MST를 찾는 크루스칼과 프림은 어떻게 다른지에 대해 알아보는 것입니다.

 

먼저 MST를 어떻게 탐색할 수 있을지 생각해볼까요?

큰 틀은 비용이 낮은 정점(간선)을 연결해 나가는 것입니다. 마치 그리디 알고리즘 같은데요.

그러나 주의해야할 부분은 연결했을 때 사이클이 발생하면 안된다는 점입니다.

또한 사이클이 발생하는지를 찾는 방법이 크루스칼과 프림 알고리즘의 큰 차이점이기도 합니다.

 

먼저 프림 알고리즘에 대해 간단히 설명한 후에 두 알고리즘의 차이에 대해 정리할게요.

 

✅ 프림 알고리즘

프림 알고리즘은 "정점 중심"으로 탐색이 진행됩니다.

임의의 시작 정점에서부터 "연결 가능한 최소 비용의" 인근 정점으로 확장해 나가는 방식인데요.

 

또한 사이클의 발생 유무는 방문 배열을 활용합니다. (크루스칼과 다른 부분입니다.)

탐색하려는 정점이 이미 방문한 정점이라면 해당 정점과 연결된 간선은 무시합니다.

 

💡 Think

그러나 문득 "방문 상태에만 의존하여 연결 여부를 결정하면, 모든 정점이 연결 안될 수 있는거 아닌가?" 라는 생각이 들었습니다.

왜냐하면 크루스칼에서 유니온 파인드가 아닌 방문체크를 적용해도 되는지 테스트 해본 결과 안되는 케이스를 발견했거든요.

크루스칼에서 안되는 케이스는 아래와 같습니다. 모든 정점은 방문 되었지만, 연결은 되지 않은 케이스입니다.

GPT 활용

그래서 프림은 방문체크로만 왜 모든 정점이 되는지 찾아본 결과 아래와 같습니다.

프림 알고리즘의 중요한 포인트는 연결된 모든 정점을 기준으로 최소 비용 간선을 연결합니다.

무슨 의미냐면, 현재 탐색중인 정점에서 인근 정점 뿐만 아니라 이전에 연결된 정점에서도 탐색하기 때문에 방문하지 않는 정점이 생길수가 없습니다.

 

가중치 값에 따라 순서가 늦어질 뿐, 방문하지 않은 정점이 있다면 언젠간 연결이 되는걸 의미합니다.

---

또한 프림은 크루스칼 알고리즘에 비해 추가적으로 알아야하는 알고리즘도 없으며, 비교적 간단하게 구현할 수 있습니다.

아래는 참조용 소스코드입니다.

우선순위 큐를 활용하셔도 된다는 점을 미리 알려드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class MSTPrimTest {
    
    static int V, adjMatrix[][]; //정점의 개수 , 인접행렬
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(bf.readLine());
        adjMatrix = new int[V][V]; //인접행렬 생성
        
        for(int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j = 0; j < V; j++) {
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 방문정점(트리정점표시)
        boolean[] visited = new boolean[V];
        int[] minEdge = new int[V];//자신과 트리의 정점들 간 최소 간선 비용.
        
        Arrays.fill(minEdge, Integer.MAX_VALUE);// 최소값 갱신 위해 큰 값으로 세팅
        minEdge[0] = 0; //임의의 0 정점을 트리 구성의 시작으로 하기 위해 세팅
        
        int result = 0; //최소신장트리 비용
        int min = 0, minVertex = 0;
        for(int c = 0; c < V; c++) {
            minVertex = -1;
            min = Integer.MAX_VALUE;
            //step 1 : 미방문(비트리) 정점중 최소간선비용의 정점을 선택
            for(int i = 0; i < V; i++) {
                if(!visited[i] && min > minEdge[i]) {
                    min = minEdge[i];
                    minVertex = i;
                }
            }
            //step2 : 방문(트리) 정점에 추가
            visited[minVertex] = true;//방문처리
            result += min;//신장트리 비용누적
            
            //step3 : 트리에 추가된 새로운 정점 기준으로 비트리 정점과의 간선비용 고려
            for(int i = 0; i < V; i++) {
                if(!visited[i] && adjMatrix[minVertex][i] != 0 && minEdge[i] > adjMatrix[minVertex][i]) {
                    minEdge[i] = adjMatrix[minVertex][i];
                }
                
            }    
        }
        System.out.println(result);
    }
    
}

 

✅ Wrap-UP

다시한번 두 알고리즘에 대한 차이를 정리하겠습니다.

크루스칼은 해당 문제를 간선 중심으로 풀어나갑니다. 정렬된 간선을 하나씩 보면서 "해당 간선을 연결해도 될까? 되면 연결하자" 인거죠.

그렇다보니 모든 정점이 연결되었는지, 사이클은 안생기는지를 못찾습니다.

이를 유니온 파인드가 빈 자리를 채워주는거구요.

 

반면에 프림은 정점 중심으로 풀어나갑니다. 현재까지 연결된 정점으로부터 "인근 정점 중 최소 비용을 연결하자" 인거죠.

이미 연결된 두 정점 사이의 연결은 하지 않기 때문에 사이클이 발생하지도 않습니다.

 

여기까지 MST 알고리즘이 뭔지, MST를 구현하는 방식인 크루스칼 알고리즘과 프림 알고리즘은 무엇인지에 대해 알아보았습니다.

 

추가적인 견해로 처음에 MST를 배울 땐 크루스칼 알고리즘과 프림 알고리즘 중 뭐가 더 좋은거야? 라는 궁금함이 있었는데요.

"간많프 간적크"라는 말이 있더라구요. 풀어 말하면 간선이 많으면 프림을 쓰고, 간선이 적으면 크루스칼을 쓰라는 의미예요.

반대로 정점이 적으면 정점 중심으로 탐색하는 프림을 쓰는게 효율이 좋겠죠.

 

혹시나 잘못된 부분 혹은 궁금한 부분이 있다면 댓글 남겨주시면 감사하겠습니다.