프로그래머스 섬 연결하기 JAVA

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

문제

해당 문제는 섬 간 다리 건설비용이 주어졌을 때 모든 섬을 연결하는 가장 최소 비용을 구하는 문제다. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

풀이

해당 문제는 보자마자 크루스칼 알고리즘을 적용하면 되겠다고 생각했다. 입력값도 엣지와 가중치가 주어지기 때문에 딱이었다. 먼저 람다식으로 2차원 배열을 비용이 작은 순서로 정렬하고 이후 해당 배열을 크루스칼 알고리즘을 적용시켜준다. 기저 조건으로 연결된 카운트가 n-1이랑 같아지면 빠져나와서 출력해주면 해결 가능하다.

코드

import java.util.Arrays;

class Solution {
	static int[] number;
	public static int solution(int n, int[][] costs) {
		int answer = 0;
		Arrays.sort(costs,(a,b) -> a[2] - b[2]); // 배열을 비용이 작은순서로 정렬 람다식
		number = new int[n];
		for (int i = 0; i < n; i++) { 
			number[i] = i;
		}
		int cnt = 0;
		for (int i = 0; i < costs.length; i++) {
			if(find(costs[i][0]) == find(costs[i][1])) // 같으면 이미 연결된 상태
				continue;
			union(costs[i][0],costs[i][1]); // 연결시켜주고
			answer+= costs[i][2]; // 비용을 추가해줌
			if(++cnt == n-1) // 연결한 갯수가 n-1개이면 모든 섬을 연결한 상태
				break;
		}
		return answer;
	}
	
	static int find(int a) {
		if(a == number[a])
			return a;
		return number[a] = find(number[a]);
	}
	
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a < b)
			number[b] = a;
		else
			number[a] = b;
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드