[Programmers] 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

문제 설명

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. MST 알고리즘 활용하기

2. 경로를 오름차순으로 정렬하기

3. 현재 노드의 부모 노드 탐색하기

4. 부모 노드가 같다면 연결되어 있다는 의미!

5. 부모 노드가 다르다면 새로운 경로를 찾았다는 것과 같음, 최단 경로로 추가하기!

import java.util.*;
class Solution {
    static int[] parent;
    public static int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        Arrays.sort(costs, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
        for(int i=0; i<n; i++) {
        	parent[i] = i;
        }
        for(int[] edge : costs) {
        	int from = edge[0];
        	int to = edge[1];
        	int cost = edge[2];
        	
        	// 각 노드의 부모 노드 찾기
        	int fromP = dfs(from);
        	int toP = dfs(to);
        	
        	// 둘이 부모 노드가 같다면, 연결되어 있다면 해당 간선은 넘어가!
        	if(fromP==toP) continue;
        	
        	// 둘이 부모 노드가 달라? 그럼 최소 비용으로 추가!
        	answer += cost;
        	parent[toP] = fromP; // 이 경로를 추가했으니 연결된 최상위 부모 노드로 갱신
        }
        
        return answer;
    }

	private static int dfs(int node) {
		if(parent[node]==node) return node;
		return parent[node] = dfs(parent[node]);
	}
}