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

문제 링크

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

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

 

이 문제는 '서로소 집합'과 '크루스칼 알고리즘'을 알고 있으면 손쉽게 풀 수 있다.

 

https://born2bedeveloper.tistory.com/29

[JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find)

 

https://born2bedeveloper.tistory.com/31

[JAVA] 크루스칼 알고리즘(Kruskal Algorithm)

 

풀이 방식은 이렇다.

 

1. costs 배열을 건설 비용을 기준으로 오름차순으로 정렬한다.

2. costs 배열을 처음 부터 돌며 연결할 양쪽 섬의 부모가 같은지 판별한다.

   2-1 부모가 같으면 해당 다리는 건설하지 않는다.

   2-2 부모가 다르면 해당 다리를 채택하여 건설한다.

3. 배열을 돌며 건설할 다리 비용을 합산한 answer을 return한다.

 

코드를 보기 전에 그림으로 간단히 과정을 살펴보자.

프로그래머스에 나온 예시로 진행해보겠다.

Costs :  [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

 

정렬된 costs에서 [0, 1, 1] 값을 꺼낸다.

 

0의 부모는 0

1의 부모는 1

부모가 겹치지 않으므로 다리를 건설한다.

 

union연산을 이용하여 섬1을 섬0 집합에 합친다.

 

그룹 0 : [섬0, 섬1]

그룹 2 : [섬2]

그룹 3 : [섬3]

 

 

 

costs에서 값 [1, 3, 1]을 꺼낸다.

 

1의 부모는 0

3의 부모는 3

부모가 겹치지 않으므로 다리를 건설한다.

 

union연산을 이용하여 섬3을 섬1 집합에 합친다.

 

그룹 0 : [섬0, 섬1, 섬3]

그룹 2 : [섬2]

 

 

 

 

 

costs에서 값 [0, 2, 2]을 꺼낸다.

 

0의 부모는 0

2의 부모는 2

부모가 겹치지 않으므로 다리를 건설한다.

 

union연산을 이용하여 섬2을 섬0 집합에 합친다.

 

그룹 0 : [섬0, 섬1, 섬2, 섬3]

 

 

 

 

 

costs에서 값 [1, 2, 5]을 꺼낸다.

 

1과 2의 부모 모두 0이다.

 

그래프를 보면 0, 1, 2가 사이클을 돌게 되는 것을 볼 수 있다. 

 

따라서 다리 건설에서 제외한다.

 

 

 

 

 

 

costs에서 값 [2, 3, 8]을 꺼낸다.

 

2와 3의 부모 모두 0이다.

 

그래프를 보면 0, 1, 2, 3이 사이클을 돌게 되는 것을 볼 수 있다. 

 

따라서 다리 건설에서 제외한다.

 

 

 

 

 

반복문을 모두 돌고 나서 건설된 다리의 경우는 아래와 같다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드와 함께 살펴보자

// 크루스칼 알고리즘 필요 (서로소)
// 건설 비용이 낮은 순으로 정렬한 후, 간선 연결을 시작한다
// 각 노드의 부모가 일치하지 않으면 채택, 일치하면 pass
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
    public int findParent(int[] parent, int node) {
        if (parent[node] == node)
            return node;
        return findParent(parent, parent[node]);
    }
    public void union(int[] parent, int node1, int node2) {
        int p1 = findParent(parent, node1);
        int p2 = findParent(parent, node2);
        
        if (p1 < p2)
            parent[p2] = p1;
        else
            parent[p1] = p2;
    } 
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int []parent = new int[n];
        
        for (int i = 0; i < parent.length; i++)
            parent[i] = i;
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int i = 0; i < costs.length; i++) {
            if(findParent(parent, costs[i][0]) != findParent(parent, costs[i][1])) { // 사이클 판단
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }
        return answer;
    }
}

 

앞서 말했듯이 크루스칼 알고리즘을 사용하면 아주 간단하게 구할 수 있다.

해당 알고리즘에 대해 처음 들어본다면 필자가 크루스칼과 서로소에 대해 올린 게시글을 참고한다면 이해하는데 도움이 될 것이다. (봐주세요 제발)

 

++수정 ) moseoh님의 피드백으로 24줄 코드를 변경하였습니다! 감사합니다 :)