프로그래머스 섬 연결하기(Level3 Java)

https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=java

프로그래머스

---

문제

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.
입출력 예

n costs return
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

문제 해결을 위한 과정

크루스컬 알고리즘은 그리디한 선택을 통해 MST(최소 신장트리)를 구할 수 있습니다.

1. 정렬: 주어진 모든 다리(간선)를 비용이 낮은 순서대로 정렬합니다.
2. 사이클 확인 (Union-Find): 비용이 낮은 다리부터 하나씩 선택하되, 현재 연결하려는 두 섬이 이미 연결되어 있는지 확인합니다.
   • 이미 같은 부모를 공유한다면(연결되어 있다면) 건너뜁니다. (사이클 방지)
   • 연결되어 있지 않다면 두 섬을 합치고(union), 비용을 더합니다.
3. 반복: 모든 다리를 확인할 때까지 반복합니다.

---

소스코드

import java.util.*;

class Solution {
    static ArrayList<Node> list = new ArrayList<>();
    static int[] parent;
    
    static int findParent(int[] parent, int x) {
        if(parent[x] != x) {
            parent[x] = findParent(parent, parent[x]);
        }
        return parent[x];
    }
    
    static void unionParent(int[] parent, int x, int y) {
        int a = findParent(parent, x);
        int b = findParent(parent, y);
        if(a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
    
    static class Node implements Comparable<Node> {
        int nodeA;
        int nodeB;
        int cost;
        
        public Node(int nodeA, int nodeB, int cost) {
            this.nodeA = nodeA;
            this.nodeB = nodeB;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n + 1];
        for(int i = 0; i < n + 1; i++) {
            parent[i] = i;
        }
        
        for(int i = 0; i < costs.length; i++) {
            int a = costs[i][0];
            int b = costs[i][1];
            int c = costs[i][2];
            
            list.add(new Node(a, b, c));
        }
        
        Collections.sort(list);
        
        for(int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            
            int a = node.nodeA;
            int b = node.nodeB;
            int c = node.cost;
            
            if(findParent(parent, a) != findParent(parent, b)) {
                answer += c;
                unionParent(parent, a, b);
            }
        }
        return answer;
    }
}