[프로그래머스] Lv3 - 섬 연결하기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

접근 방식

문제를 다른말로 해석하면, 문제가 모든 정점을 연결하는 간선들의 최소 비용 집합을 구하는 것입니다.

이 문제는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 문제라고 판단을 했습니다.

 

최소 신장 트리를 찾는 방법은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

프림 알고리즘이 크루스칼 알고리즘보다 비교적 더 쉽다고 판단이 되어 프림 알고리즘을 선택했습니다.

 

프림 알고리즘의 흐름은 어떻게 될까요?

1. 시작 정점을 선택
2. 우선순위 큐에서 가장 가중치가 작은 간선을 선택
3. 해당 간선이 연결하는 정점이 MST에 포함되지 않았다면 추가
4. 새로운 정점에서 갈 수 있는 간선들을 우선순위 큐에 삽입
5. MST가 완성될 때까지 반복

 

예제를 분석하며 프림 알고리즘이 합당한지 보겠습니다. 예제는 아래와 같습니다.

 

시작하는 정점은 0번째 노드를 선택하겠습니다.

 

먼저, 0번째 노드가 우선순위 큐에 들어가게 됩니다.

(단, 실제 우선순위 큐는 트리 구조를 사용하지만, 보기 편하게 Queue 구조로 나타냈습니다.)

 

0번 노드부터 출발했으니, 0번 노드를 방문처리 합니다.

 

 

0번 노드에 연결된 노드는 1번과 2번 노드가 있습니다. 두 노드를 우선순위 큐에 넣어줍니다.

우선순위 큐는 거리를 기준으로 가장 짧은 거리(가중치)를 맨 앞에 오도록 합니다.

 

방문한 노드 : [0번]

 

그 다음 1번 노드를 빼줍니다. 빼준 1번 노드는 방문처리를 합니다. 1번 노드와 연결된 노드는 0번, 2번, 3번 노드가 있습니다. 0번 노드는 이미 방문했으므로, 2번 노드와 3번노드를 우선순위 큐에 넣어 줍니다. 3번 노드의 가중치가 제일 작기 때문에, 큐의 맨 앞으로 오게 됩니다.

 

방문한 노드 : [0번, 1번]

 

그 다음 3번 노드를 빼줍니다. 빼준 3번 노드는 방문처리를 합니다. 3번 노드와 연결된 노드는 1번과 2번 노드가 있지만, 1번 노드는 이미 방문했으므로, 2번 노드를 우선순위 큐에 넣어 줍니다.

 

방문한 노드[0번,1번,3번]

 

그 다음 맨 앞에 있는 2번 노드를 빼줍니다. 빼준 2번 노드는 0번,1번,3번 노드와 연결되어 있지만, 0번,1번,3번 노드는 이미 방문을 했으므로 우선순위큐에 아무것도 추가해주지 않습니다.

 

방문한 노드[0번,1번,3번,2번]

 

그 다음은 우선순위 큐에 남은 노드들과 연결된 노드들은 이미 방문한 노드이기에 우선순위 큐가 비워지게 되고, 프림 알고리즘이 종료됩니다.

 

 

0(0번 방문 거리) + 1(1번 방문 거리) + 1(3번 방문 거리) + 2(2번 방문 거리) = 4

최종적으로 4의 값이 나오게 됩니다.

 

프림 알고리즘을 사용해 MST를 풀이한 코드는 다음과 같습니다.

 

풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        List<List<Node>> graph = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int[] cost: costs) {
            int start = cost[0];
            int next = cost[1];
            int weight = cost[2];
            
            graph.get(start).add(new Node(next,weight));
            graph.get(next).add(new Node(start,weight));
        }
        
        boolean[] visited = new boolean[n];
        
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));
        
        pq.add(new Node(0,0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            
            if(visited[cur.number]) {
                continue;
            }
            
            visited[cur.number] = true;
            answer += cur.weight;
            
            for(Node nextNode : graph.get(cur.number)) {
                if(!visited[nextNode.number]) {
                    pq.add(nextNode);
                }
            }
        }
        
        return answer;
    }
    
    class Node {
        int number;
        int weight;
        
        public Node(int number, int weight) {
            this.number = number;
            this.weight = weight;
        }
    }
}

 

출력 결과