[프로그래머스/JAVA] 고득점Kit > 탐욕법(Greedy) > 섬 연결하기 (by 다알쥐AI)

고득점Kit > 탐욕법(Greedy) > 섬 연결하기

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

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

---

[간단설명]

n-1개 만큼 다리를 만들었을 때, 최소비용 구하는 문제

ㄴ 최소비용 신장트리 문제

 

[접근방법]

 

1. find & union 함수를 만든다

2. 루트 노드를 만들고, 초기값 세팅

3. costs를 비용(cost) 오름차순 정렬한다

4. 크루스칼 알고리즘을 이용하여 순회한다

    1) a,b의 루트 노드를 찾는다

    2) a,b의 루트 노드가 같지 않으면, 루트 노드를 합친다

    3) cost 값을 더해준다

 

[주의사항]

크루스칼 알고리즘을 모르면 풀기 어렵지만, 다양한 풀이법으로도 풀어보자

 

[소스공개]

import java.util.*;
class Solution {
    // 루트 노드
    public static int[] root;
    // 루트 노드 찾기
    public int find(int n){
        if(root[n]==n) return n;
        else return root[n]=find(root[n]);
    }
    // 집합 구성(부모 노드가 서로 다르면 하나의 루트 노드로 만든다)
    public void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b) root[b]=a;
    }
    
    // 최소비용 신장트리
    public int solution(int n, int[][] costs) {
        // 루트 노드 초기값 세팅
        // root : [0,1,2,3]
        root = new int[n];
        for(int i=0;i<n;i++) {
            root[i]=i;
        }
        
        // 비용(cost) 오름 차순 정렬
        // costs : [0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]
        Arrays.sort(costs,(o1,o2)->o1[2]-o2[2]);        
        int cost=0;
        for(int i=0;i<costs.length;i++){
            int a = costs[i][0]; // 첫번째 섬
            int b = costs[i][1]; // 두번째 섬
            int c = costs[i][2]; // 비용(cost)
            
            // 루트 노드가 서로 다르면
            // 하나의 루트 노드로 만든다
            // 즉, 루트 노드가 같으면 순회하지 않는다
            // ㄴ> 비용으로 정렬했기 때문에, 같은 루트에서 최소 비용은 이미 뽑혔다
            // root : [0,1,2,3]
            // costs : [0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]
            // -----------------------------------------------
            // [1단계]
            // a = root[0] = 0
            // b = root[1] = 1
            // union = root[1] = 0
            // cost = 0+1 = 1
            // -----------------------------------------------
            // [2단계]
            // a = root[1] = 0
            // b = root[3] = 3
            // union = root[3] = 0
            // cost = 1+1 = 2
            // -----------------------------------------------
            // [3단계]
            // a = root[0] = 0
            // b = root[2] = 2
            // union = root[2] = 0
            // cost = 2+2 = 4(정답)
            // -----------------------------------------------
            // [4단계]
            // a = root[1] = 0
            // b = root[2] = 0
            // 루트 노드가 일치하여 SKIP
            if(find(a)!=find(b)){
                union(a,b); // 루트 합치기
                cost+=c; // 비용 추가
            }
        }
        return cost;
    }
}

 

[실행결과]