[알고리즘] 프로그래머스 섬 연결하기 -그리디, 최소신장트리- 자바

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

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

프로그래머스 LV3 그리디 유형의 선 연결하기 문제입니다.

 

섬이 여러개 있는데 최소 비용으로 모든 섬을 연결해야합니다.

전형적인 최소신장트리 문제로 크루스칼 알고리즘을 사용하게 됩니다. 오랜만에 푸는 유형이었습니다. 

youngest-programming.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EC%9C%A0%EB%8B%88%EC%98%A8%ED%8C%8C%EC%9D%B8%EB%93%9C%2C%20%EC%B5%9C%EC%86%8C%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%AC

'알고리즘/유니온파인드, 최소신장트리' 카테고리의 글 목록

이전에 풀었던 유형이므로 설명은 생략하도록 하겠습니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    private static int[] parent;
    private static List<Edge> edgeList = new ArrayList<>();

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < costs.length; i++) {
            int start = costs[i][0];
            int end = costs[i][1];
            int weight = costs[i][2];
            edgeList.add(new Edge(start, end, weight));
        }
        Collections.sort(edgeList); //가중치 오름차순 정렬
        //최소신장트리 탐색
        for (int i = 0; i < edgeList.size(); i++) {
            Edge edge = edgeList.get(i);
            if (!isSameParent(edge.start, edge.end)) { //사이클이 발생하지 않은 경우 연결
                answer += edge.weight;
                union(edge.start, edge.end); //연결
            }
        }
        return answer;
    }

    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }

}

 

 

 

 

 

시간이 부족하여 몇일간 공부를 못했는데 다시 시작해야겠습니다.

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!