[알고리즘]프로그래머스 42861번 - 섬 연결하기

프로그래머스 42861번 - 섬 연결하기

프로그래머스 42861번 - https://programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스 42861번 - https://programmers.co.kr/learn/courses/30/lessons/42861

 

요구사항

1. 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 반환하라.

2. A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

요구사항 분석 및  풀이과정

1. 이 문제는 전형적인 최소 스패닝 트리 문제입니다. 최소 스패닝 트리 문제는 크루스칼 알고리즘 또는 프림 알고리즘으로 해결 가능합니다.

2. 저는 서로소 집합(Union-Find)을 이용한 크루스칼 알고리즘을 사용할 할 것입니다. 크루스칼 알고리즘에 대해서는 따로 설명하지 않겠습니다.

3. 섬 사이에 다리를 건설하는 비용을 기준으로 내림차순 정렬하여, 비용이 적은 다리부터 사이클이 형성되지 않도록 N - 1 개의 다리를 선택하면 모든 섬이 서로 통행 가능하도록 연결할 수 있습니다.

 

소스코드 작성

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    
    private static class Dsu {

        private final int[] parent;

        public Dsu(int size) {
            this.parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] == x) {
                return x;
            }

            parent[x] = find(parent[x]);
            return parent[x];
        }

        public boolean union(int x, int y) {
            int parentX = find(x);
            int parentY = find(y);

            if (parentX == parentY) {
                return false;
            }

            parent[parentY] = parentX;
            return true;
        }
    }
    
    public int solution(int n, int[][] costs) {
        Arrays.sort(costs, Comparator.comparingInt(cost -> cost[2]));
        
        Dsu d = new Dsu(n);
        int result = 0;
        int count = 0;

        for(int[] cost : costs) {
            if (count == n-1) {
                break;
            }
            
            if (d.union(cost[0], cost[1])) {
                result += cost[2];
                count++;
            }
        }
        
        return result;
    }
}

 

결과

 

소스코드 깃허브 주소

링크