탐욕법 - 섬 연결하기

 

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

 

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

 

 

풀이

여러개의 노드가 존재할 때 연결된 노드들을 같은 집합 구성원으로 묶어주는 알고리즘이다.

 

1. costs 배열을 건설 비용을 기준으로 오름차순으로 정렬한다.

2. costs 배열을 처음 부터 돌며 연결할 양쪽 섬의 부모가 같은지 판별한다.

  2-1. 부모가 같으면 해당 다리는 건설하지 않는다.

  2-2 부모가 다르면 해당 다리를 채택하여 건설한다.

3. 배열을 돌며 건설할 다리 비용을 합산한 answer을 return한다.

 

import java.util.*;

class Solution {
    // 유니온 파인드에서 부모 노드를 찾는 함수
    public int findParent(int[] parent, int node) {
        if (parent[node] == node) {
            return node;
        }
        return parent[node] = findParent(parent, parent[node]);  // 경로 압축 기법
    }

    // 두 섬을 연결하는 함수 (유니온 연산)
    public void union(int[] parent, int node1, int node2) {
        int root1 = findParent(parent, node1);
        int root2 = findParent(parent, node2);
        
        if (root1 != root2) {
            parent[root2] = root1;  // 두 노드의 부모를 동일하게 설정
        }
    }

    public int solution(int n, int[][] costs) {
        // 간선들을 비용 순으로 정렬
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);

        // 유니온 파인드용 배열 초기화 (각 섬의 부모를 자기 자신으로 초기화)
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int answer = 0;
        int edgeCount = 0;  // 연결된 간선의 수

        // 비용이 낮은 간선부터 연결 시도
        for (int[] cost : costs) {
            int island1 = cost[0];
            int island2 = cost[1];
            int bridgeCost = cost[2];

            // 두 섬이 이미 연결되어 있지 않다면 (같은 부모를 가지지 않으면)
            if (findParent(parent, island1) != findParent(parent, island2)) {
                union(parent, island1, island2);  // 두 섬을 연결
                answer += bridgeCost;  // 비용을 추가
                edgeCount++;

                // n-1개의 간선이 연결되면 모든 섬이 연결된 것이므로 종료
                if (edgeCount == n - 1) {
                    break;
                }
            }
        }

        return answer;  // 최소 비용 반환
    }
}

 

 

 

해당 알고