문제 링크

Greedy 풀이

처음엔 Greedy로 풀었었는데,
다시 풀 때는 MST(최소 스패닝 트리)알고리즘을 한번 적용해보았다.(Kruskal 알고리즘)

먼저 그리디의 경우에는 양방향으로 탐색가능하게 만들고, 최소의 값을 계속해서 찾았다.
그렇게 while문을 돌아 n번 채워지면 연결이 된 것으로 가중치의 최소값을 구할 수 있다.

코드(Greedy)

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[][] adj = new int[n][n];
        for(int i = 0; i < costs.length; i++) {
            adj[costs[i][0]][costs[i][1]] = adj[costs[i][1]][costs[i][0]] = costs[i][2];
        }
        boolean[] visit = new boolean[n];
        List<Integer> connect = new ArrayList<>(n+1);
        connect.add(0);
        visit[0] = true;
        while(connect.size() < n) {
            int min = Integer.MAX_VALUE;
            int minIdx = -1;
            for(int island = 0; island < connect.size(); island++) {
                int i = connect.get(island);
                for(int j = 0; j < n; j++) {
                    if(!visit[j] && i != j && adj[i][j] > 0 && adj[i][j] < min) {
                        min = adj[i][j];
                        minIdx = j;
                    }
                }
            }
            visit[minIdx] = true;
            connect.add(minIdx);
            answer += min;
        }
        return answer;
    }
}

MST(Kruskal) 풀이

스패닝 트리란?
그래프에서 일부 간선을 선택해서 만든 트리(그래프 -> 트리)

최소 스패닝 트리(MST)란?
스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리

MST 알고리즘에는 Prim과 Kruskal이 있는데 난 그 중에서 Kruskal을 사용하여 풀 수 있었다.

Kruskal

• 가중치가 작은 Edge부터 순서대로 살펴본다.
• Edge e가 (u,v,c) 일 때, u와 v가 다른 집합이면 e를 MST에 추가한다.
• 이때, 다른 집합인지 같은 집합인지 찾기 위해 재귀를 사용하여 찾아 연결한다.(Union-Find)

  여기서 다른 집합이란 초록색 간선으로 연결되어있지 않은 것을 의미

0) 처음

1) 2(u)-5(v)-1(c) 연결

2) 3(u)-4(v)-1(c) 연결

3) 1(u)-2(v)-2(c) 연결

4) 6(u)-7(v)-2(c) 연결

5) 1(u)-5(v)-3(c) 연결 실패 [이유: 같은 집합임] -> 2(u)-4(v)-3(c) 연결

6) 2(u)-3(v)-4(c) 연결 실패 [이유: 같은 집합임] -> 3(u)-7(v)-4(c) 연결

7) MST 완성
탐색하면서 연결선의 최소값을 찾으며 스패닝 트리를 만든다.

시간복잡도 - O(ElgE)
1. 정렬 (O(E lgE))
2. Union-Find (O(E))

코드(Kruskal)

import java.util.*;
class Solution {
    static class Edge {
        int start;
        int end;
        int cost;
        public Edge() {
            this(0,0,0);
        }

        public Edge(int s,int e,int c) {
            this.start = s;
            this.end = e;
            this.cost = c;
        }
    }

    public static int solution(int n, int[][] costs) {
        int ans = 0;

        int[] p = new int[n+1];
        for (int i=0; i<=n; i++) {
            p[i] = i;
        }

        ArrayList<Edge> a = new ArrayList<>();
        for( int[] cost : costs ) {
            a.add( new Edge(cost[0],cost[1],cost[2]));
        }
        a.sort((e1,e2) -> e1.cost - e2.cost);

        for( Edge e : a ) {
            int x = find(p,e.start);
            int y = find(p,e.end);

            if( x != y ) {
                union(p,x,y);
                ans += e.cost;
            }
        }

        return ans;
    }

    // 찾기
    static int find(int[] p, int a) {
        if( a == p[a] )
            return a;

        return p[a] = find(p,p[a]);
    }

    // 연결
    static void union(int[] p, int a, int b) {
        a = find(p,a);
        b = find(p,b);
        p[a] = b;
    }
}

참고

• https://brenden.tistory.com/33