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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 점들의 연결 정보를 통해 최소 신장 트리를 구성

 해당 문제는 문제 자체에서 요구하는 바가 섬들 간의 최소 신장 트리를 구성하고 총 거리를 반환하는 것이기 때문에, 최소 신장 트리 생성 알고리즘을 적용하면 된다. 여기서 나는 크루스칼 알고리즘을 적용해 문제를 해결했는데, 거리 간 비용의 정렬을 쉽게 하고자 우선순위 큐를 사용하고, 해당 큐에 넣을 정보 클래스 간의 compareTo 함수를 오버라이딩했다. 추가로 필요한 union-find 문제의 경우 집합(부모)의 대표를 저장하는 배열과 해당 집합(부모)을 find하는 함수를 간단히 구현해 해결했다.

 

class Solution {
    int[] union;

    public int solution(int n, int[][] costs) {
        PriorityQueue<Infor> pq = new PriorityQueue<>(); //크루스칼 알고리즘을 위한 우선순위 큐
        int answer = 0;
        union = new int[n];
        Arrays.fill(union, -1);

        for (int i = 0; i < costs.length; i++) {
            Infor infor = new Infor(costs[i][0], costs[i][1], costs[i][2]);
            pq.add(infor);
        }

        for (int i = 0; i < n - 1; ) { //n 개 섬의 최소 신장 트리기 때문에 n-1번만 하면 된다.
            Infor infor = pq.poll();
            int islandAParent = findParent(infor.islandA), islandBParent = findParent(infor.islandB);

            if (islandAParent != islandBParent) {//집합이 같으면 사이클이기에 넘어간다.
                answer += infor.cost;
                union[islandBParent] = islandAParent;
                ++i;
            }
        }

        return answer;
    }

    int findParent(int island) {//집합(부모) find 함수
        if (union[island] == -1) {
            return island;
        } else {
            return union[island] = findParent(union[island]);
        }
    }

    class Infor implements Comparable<Infor> {//정보 클래스 
        int islandA, islandB, cost;

        public Infor(int islandA, int islandB, int cost) {
            this.islandA = islandA;
            this.islandB = islandB;
            this.cost = cost;
        }

        @Override
        public int compareTo(Infor o) {//우선 순위 큐에 적용하기 위한 비교 함수
            return this.cost < o.cost ? -1 : 1;
        }
    }
}

결과