[프로그래머스] 섬 연결하기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

2. 입력

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

3. 예제

n	cost	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

4. 풀이

이번 문제는 Kurskal 알고리즘을 알고 있다면 바로 풀 수 있는 문제였습니다.

 

문제에서 섬이 있고 섬과 섬을 이어주는 다리가 있다고 하였으므로 섬은 노드 다리는 간선으로 볼 수 있습니다.

 

그럼 섬과 다리들을 연결하여 그래프를 만들 수 있습니다.

 

이렇게 만들어진 그래프에서 간선들을 연결하여 최소 비용으로 모든 노드가 연결되도록 하는 것이므로 최소비용 신장 트리를 찾는 것과 동일합니다.

 

최소비용 신장 트리를 구하는 알고리즘인 Kruskal 알고리즘을 그대로 적용하면 됩니다.

 

여기서는 간단하게 Kruskal 알고리즘을 설명하도록 하겠습니다.

 

먼저 다리의 비용을 내림차순으로 정렬합니다.

 

예제를 예로 들면 위 이미지처럼 정렬됩니다.

 

이후 다리 비용이 가장 작은 다리부터 시작하여 노드를 이어 나갑니다.

 

이후 이어진 노드(섬) 2개는 하나의 집합에 속하게 됩니다.

 

즉 예제의 첫 다리인 0과 1을 연결하면 1번 노드는 0번 노드 집합에 포함됩니다.

 

이렇게 모든 노드를 연결하면서 연결된 노드(섬)의 집합을 변경합니다.

 

이때 특정 집합에서 출발하여 도착 집합이 출발 집합과 같은 집합이면 사이클이 발생한 것으로 다리를 연결할 수 없으므로 해당 다리는 연결에서 제외시킵니다.

 

이렇게 모든 간선을 확인하면 최종 최소비용 신장 트리의 비용을 구할 수 있게 되고 해당 문제를 풀 수 있습니다.

 

Kurskal 알고리즘은 블로그에 자세히 작성되어 있습니다. 참고하시면 이번 문제를 아주 쉽게 풀 수 있을 것 같습니다.

5. 코드

전체 코드는 Git에 있습니다.

private int[] parent;
private int[] parent;
public int solution(int n, int[][] costs) {
	parent = new int[n];
	for(int i=0; i<n; i++)
		parent[i] = i;

	Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));

	int answer = 0;
	for (int[] cost : costs) {
		if (getParent(cost[0]) != getParent(cost[1])) {
			answer += cost[2];
			merge(cost[0], cost[1]);
		}
	}

	return answer;
}

public int getParent(int node){
	if(parent[node] == node)
		return node;
	else
		return getParent(parent[node]);
}

public void merge(int startNode, int endNode){
	int startParent = getParent(startNode);
	int endParent = getParent(endNode);

	if(startParent > endParent)
		parent[startParent] = endParent;
	else
		parent[endParent] = startParent;
}