[프로그래머스 : 레벨 3] 섬 연결하기 : 크루스칼 알고리즘 (Java)

이번 문제는 크루스칼 알고리즘을 직접구현하고 나서 문제를풀었더니 금방 풀렸다.

내 스스로 풀었다고 해야할지 아니면 답을 봤다고 해야할지 모르겠지만 어찌됐건 

크루스칼 알고리즘을 배워서 적용시키니 금방 풀렸다.

 

문제부터 보자.

 

문제 설명

 

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

 

 

해당 문제는 노드들을 최소의 비용으로 방문할수 있는 최소 비용을 구하고 있다.

 

그걸 우리는 MST(최소 비용 신장트리) 라고 하는데 해당 비용은 크루스칼 알고리즘을 통해서 쉽게 구현할수 있다.

크루스칼 알고리즘과 관련해서는 아래링크를 참조해서 보면 될것 같다.

https://wpioneer.tistory.com/117

[자료구조] 크루스칼 알고리즘(Kruskal Algorithm)

 

이번 소스에 대한 풀이는 위의 링크에 설명이 다 되어 있기때문에 생략하고 소스만 올리겠다.

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
		int[] parent = new int[n];
		
		
		for(int i = 0; i<n; i++) {
			parent[i] = i;
		}
		
        Arrays.sort(costs, (o1,o2)->{return o1[2]-o2[2];});
        
        
        int mst = 0;
        
        for(int i = 0; i<costs.length;i++) {
        	int x = costs[i][0];
        	int y = costs[i][1];
            int cost = costs[i][2];
        	if(checkLine(x, y, parent)) {
        		continue;
        	}else {
        		answer+=cost;
        		union(x, y, parent);
        	}
        }
        
        return answer;
    }
    
	public void union(int x, int y, int[] parent) {
		x = find(x, parent);
		y = find(y, parent);
		
		if(x<y) {
            parent[y] = x;
		}else{
            parent[x] = y;
        }
	}
	
	//여기선 부모 노드의 값을 리턴해주면 된다.
	public int find(int x, int[] parent) {
		if(x == parent[x]) {
			return x;
		}else { 
			return find(parent[x],parent);
		}
	}

	public boolean checkLine(int x, int y, int[] parent) {
		
		x = find(x,parent);
		y = find(y,parent);
	
		return x==y;
	}
}