그리디. 최소 스패닝 트리

문제

그래프의 모든 정점을 연결하는 부분 그래프 중에서 최소 가중치를 리턴하시오.

해결방향성

최소 스패닝 트리중 크루스칼, 프림 중 아무거나 써도된다. 일단 나는 크루스칼 & 유니온 파인드로 해결하였다. 크루스칼을 사용하기 위해서 가중치의 합을 오름차순으로 정렬한다.
1. 크루스칼은 간선 가중치에 초점을 맞추기때문에, 그래프를 연결하여 우선순위큐를 사용하는 프림과 달리, 그래프를 연결하지않아도된다.
2. 가중치를 오름차순으로 정렬후, 유니온 파인드를 쓰기위해 부모배열을 자기자신으로 초기화, total 가중치의 합을 두고, 모든 간선을 순회를 돌린다.
3. 그 후, 시작점과 종점의 부모를 찾아, 둘이 같으면 가중치에 포함을 시키지않고, 다른 그래프에속하면 서로 연결한다.(부모를 한쪽으로 몬다.)
그럼 끝.

코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int V, E;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        int[][] weight = new int[E][3]; // 0 : 시작 1 : 도착 2 : 가중치
        // 가중치 합이 최소니까 크루스칼?
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            weight[i][0] = Integer.parseInt(st.nextToken());
            weight[i][1] = Integer.parseInt(st.nextToken());
            weight[i][2] = Integer.parseInt(st.nextToken());
        }

        // 가중치 오름차순 정렬
        Arrays.sort(weight, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        // 예는 부모노드가 같은거만 나왔지만 다른게 나온다면?
        // 유니온 파인드
        parent = new int[V + 1]; // 1 ~ V

        // 부모노드 모두 자신으로 초기화
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        // 최소 가중치로 연결할수있는 가중치의 총 합
        int total = 0;

        // edge순회 : edge중에서
        for (int[] edge : weight) {
            // 각각의 정보 저장
            int from = edge[0];
            int to = edge[1];
            int cost = edge[2];

            // 두 정점의 부모를 찾는다.
            int fromParent = findParent(from);
            int toParent = findParent(to);

            // 같은 그래프에 속함 (두 부모노드가 같으면)
            if (fromParent == toParent) continue; // 연결하지않는다.
            
            total += cost;
            // 다른 그래프면 도착점에 시작점을 연결
            parent[toParent] = fromParent;
        }

        bw.write(String.valueOf(total));


        bw.flush();
        br.close();
        bw.close();
    }

    private static int findParent(int node) {
        // parent[node]가 node와 같아질때 return node.
        if(parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }
}

결론

프림으로 풀어도 해결가능한듯하다.