[Programmers] 섬 연결하기 (Java)

1.  문제 링크

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

2.  문제

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

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

3.  제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    static int[] parents;
	public static int solution(int n, int[][] costs) {
		parents = new int[n];
		for(int node = 0; node < n; node++) parents[node] = node;
		Arrays.sort(costs, new Comparator<int[]>() {
			public int compare(int[] c1, int[] c2) {
				return c1[2] - c2[2];
			}
		});
		int idx = 0, minLen = 0;
		for(int i = 0; i < n - 1; i++) {
			int[] edge = costs[idx];
			if(isSameParents(edge[0], edge[1])) {
				i--;
				idx++;
				continue;
			} else {
				union(edge[0], edge[1]);
				minLen += edge[2];
			}
		}
		return minLen;
	}
	
	static int findParents(int node) {
		if(parents[node] == node) return node;
		return parents[node] = findParents(parents[node]);
	}
	
	static void union(int node1, int node2) {
		int parent1 = findParents(node1), parent2 = findParents(node2);
		if(parent1 != parent2) {
			if(parent1 < parent2) parents[parent2] = parent1;
			else parents[parent1] = parent2;
		}
	}
	
	static boolean isSameParents(int node1, int node2) {
		int parent1 = findParents(node1), parent2 = findParents(node2);
		if(parent1 == parent2) return true;
		return false;
	}
}

5. 접근

• 모든 섬이 서로 통행 가능하면서 최소 비용으로 섬을 건설한다는 뜻은 모든 노드들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리인 최소 스패닝 트리를 구하는 것과 같은 뜻이 됩니다.
• 그렇기 때문에 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 구합니다.
  • 우선 주어진 다리들을 건설할 때 드는 비용의 오름차순으로 정렬합니다.
  • 섬의 개수가 n개일 때, n - 1개의 다리를 고르는데, 비용의 오름차순으로 정렬한 순서대로 각 다리를 확인하면서 n - 1개의 다리를 고릅니다.
  • 다리를 고를 때, 사이클이 생긴다면 해당 다리는 고르지 않고 다음 다리로 넘어갑니다.
    • 사이클이 생기는지 확인할 때에는 Union-Find를 이용하여 해당 다리의 시작섬과 끝섬이 같은 부모인지 확인하는 것으로 사이클이 생기는지 확인합니다.
• 위와 같이 n - 1개의 다리를 골랐을 때, 각 다리의 비용을 더해 이를 반환합니다.