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

❓문제설명

섬 연결하기

프로그래머스

---

🔍문제해석

어떤걸 풀어야 할까?

• n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구하자
• int n과 이차원배열 costs이 주어진다.
• 양방향으로 이동 가능하고, 연결할 수 없는 섬은 주어지지 않는다.

---

🧐문제풀이

• 알고리즘 선택최소의 비용으로 모든 노드를 방문해야하기에 그리디알고리즘 > 프림 알고리즘 선택

* 프림 알고리즘

• 정의: 프림 알고리즘은 특정 그래프에서 최소 신장 트리(MST)를 찾기 위한 그리디 알고리즘의 일종. 그래프의 노드를 연결하는 간선 중에서 매 단계마다 최소 비용의 간선을 선택하여 트리를 확장함.
• 특징:
  • 항상 연결된 그래프에서 작동하며, 모든 노드를 포함하는 트리를 생성한다.
  • 매 단계에서 비용이 가장 낮은 간선을 선택함으로써 전체 비용을 최소화한다. 주로 우선순위 큐를 사용한다.

 

---

！제출코드

1. 인접리스트를 생성하여 노드간 간선, 이동 cost를 저장한다.
2. 도착 노드와 cost를 담을 클래스 생성한다.
3. 우선순위 큐에 담겼을때의 정렬조건을 지정한다. (cost 오름차순)
4. 간선정보를 담을 우선순위 큐와 방문 체크를 할 배열 생성한다.
5. 0번노드 부터 방문
6. 클래스에 지정한 정렬순서대로 queue의 원소 중 가장 cost가 적은 객체가 리턴된다.
7. 이미 방문한 노드는 스킵하고, 처음 방문한 노드에 대해서만 cost를 더한다.
8. 이동할 노드를 queue에 담는다.
9. 계산된 cost 리턴

import java.util.*;

class Solution {

       public static int solution(int n, int[][] costs) {
       
        ArrayList<ArrayList<Bridge>> bridges = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {bridges.add(new ArrayList<>()); }
        // (1)
        for (int[] cost : costs) {
            int from = cost[0], to = cost[1], c = cost[2];
            bridges.get(from).add(new Bridge(to, c));
            bridges.get(to).add(new Bridge(from, c));
        }
        // (4)
        PriorityQueue<Bridge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[n];
        // (5)
        int totalCost = 0;
        visited[0] = true;
        
        // (6)
        for(Bridge bridge : bridges.get(0)) {
            pq.offer(bridge);
        }
        
        while(!pq.isEmpty()) {
            // (6)
            Bridge bridge = pq.poll();
            
            // (7)
            if(!visited[bridge.to]){
                visited[bridge.to] = true;
                totalCost += bridge.cost;
                
                for(Bridge next : bridges.get(bridge.to)) {
                    pq.offer(next);
                }
            }
        }
        // (8)
        int answer = totalCost;
        return answer;
    }
}
// (2)
class Bridge implements Comparable<Bridge> {
    int to;
    int cost;

    public Bridge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
    // (3)
    @Override
    public int compareTo(Bridge o) {
        return this.cost - o.cost;
    }
}