[프로그래머스 고득점 kit]탐욕법 Level3 섬 연결하기

문제 설명

 

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

 

 

접근 방법

문제를 보았을 때 예전에 배운 알고리즘으로 바로 해결할 수 있을 것이라 생각했지만, 1년 전에 정리하고 제대로 본 적이 없어 알고리즘이 구체적으로 기억나지 않았다. 따라서 흐릿한 기억을 바탕으로 체계적으로 생각해 보기로 하였다.

 

1. 어떻게 최소 비용을 구할 것인가?

 

섬과 섬을 연결하는 다리를 건설하는 최종 비용을 최소화하기 위해서는 각 다리 중 가장 낮은 비용을 가지는 것 부터 건설해야할 것이다.

 

비용을 기준으로 정렬을 하거나 우선순위 큐를 사용한다.

 

2. Cycle은 허용 되는가?

 

싸이클이 허용될 경우 한 섬으로 이동하는 경로가 2개 이상이 될 수 있기 때문에 건설 비용이 최소가 될 수 없을 것 이다.

 

부모를 가리키는 배열을 사용한다. 먼저 부모 배열을 각자 자신을 가리키도록 초기화한다. 그리고 다리가 건설되면 더 작은 번호를 가지는 섬이 부모가 되고 나머지 섬이 자식이 된다.

 

나중에 알아보니 크루스칼 알고리즘이었다. 학기가 끝나면 다시 정리해야겠다.

 

 

소스 코드

import java.util.*;
class Solution {
    public static class Edge implements Comparable{
        int start;
        int end;
        int weight;
        Edge(int start, int end, int weight){
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Object o){
            Edge e = (Edge)o;
            return this.weight - e.weight;
        }
        public String toString(){
            return "start: " + this.start +"  end: " + this.end + "  weight: " + this.weight;
        }
        
    }
    public int solution(int n, int[][] costs) {
        int answer = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] parent = new int[n];
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
        for(int[] cost : costs){
            pq.offer(new Edge(cost[0], cost[1], cost[2]));
        }
        
        while(n > 1){
            Edge e = pq.poll();
            if(findSet(e.start, parent) != findSet(e.end, parent)){
                answer += e.weight;
                n--;
                union(e.start, e.end, parent);
            }
        }       
        return answer;
    }
    public void union(int n, int m, int[] parent){
        int x = findSet(n, parent);
        int y = findSet(m, parent);
        
        if(x < y){
            parent[y] = x;
        } else {
            parent[x] = y;
        }
    }
    public int findSet(int num, int[] parent){
        if(parent[num] == num){
            return num;
        }
        return findSet(parent[num], parent);
    }
}