[3124] 최소 스패닝 트리 in Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb 

SW Expert Academy

---

문제 요약

 - 최소 스패닝 트리의 가중치를 출력- c는 음수일 수도 있고, 절대값이 1,000,000을 넘지 않는다.(long 타입으로 선언)

 

---

문제 접근 방식

최소 신장 트리 (MST = 최소 스패닝 트리)

 :  n개의 정점을 모두 연결하기 위해 n-1개의 간선을 선택하여 만든 트리(무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리)

 

 

최소 스패닝 트리를 계산하는 알고리즘으로

Kruskal's algorithm과 Prim's algorithm이 있다.

 

---

(1) Kruskal's algorithm (크루스칼 알고리즘)

: 간선을 하나씩 선택해서 MST를 찾는 알고리즘!

 

(순서)

1. 최초, 모든 간선을 가중치에 따라서 오름차순으로 정렬함

2. 가중치가 가장 낮은 간선부터 트리를 증가시킨다.

(만약, 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다)

3. N-1개의 간선이 선택될 때까지 2번 과정을 반복한다.

 

- ArrayList와 Union-FindSet, MakeSet을 이용한다.

 

MakeSet

private static void makeSet() {
        for (int i = 0; i <= N; i++) {
            parents[i]=i;
        }
    }

 

Union 

private static void union(int a, int b) {
        int aParents=findSet(a);
        int bParents=findSet(b);
        if(aParents<bParents) parents[bParents]=aParents; // a,b를 넣어서 오류남
        else parents[aParents]=bParents;
}

 

 

FindSet

private static int findSet(int x) {
        if (parents[x]==x) return x;
        else return parents[x]=findSet(parents[x]);
    }

---

 

(2) Prim's algorithm (프림 알고리즘)

: 하나의 정점에서 연결된 간선들 중에서 하나씩 선택해나가며 MST를 만들어가는 알고리즘

 

(순서)

1. 임의 시작 정점을 선택함

2. 선택한 정점과 인접한 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택함

3. 모든 정점이 선택될때까지 1번, 2번 과정을 반복한다. 

 

 

 

이 문제에서는 Kruskal 알고리즘을 사용하여

문제를 풀었다.

 

---

시행착오

정점과 가중치를 new int[] 배열로 넣는 과정에서 오류가 발생했다.

그래서 new int[] 배열이 아닌 Edge라는 클래스를 만들어서

클래스 형식의 데이터를 보관하였다.

 

---

소스 코드

 

package day_0823;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Solution_3124_7조 {
    static int V; // 정점의 개수
    static int E ; // 간선의 개수
    static int[] parents; // 대표자 보관 배열
    
    static class Edge implements Comparable<Edge>{
        int from, to, weight;
        
        public Edge(int from, int to, int weight) {
            super();
            this.from = from; 
            this.to = to;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return this.weight!=o.weight? this.weight-o.weight : o.weight-this.weight; // 가중치 기준 오름차순 정렬
        }
    }
    
    private static void makeSet() {
        for (int i = 0; i <= V; i++) {
            parents[i]=i;
        }
    }
    
    private static int findSet(int a) {
        if (parents[a]==a) return a;
        return parents[a]=findSet(parents[a]);
    }
    
    private static boolean union(int a, int b) {
        int aParents=findSet(a);
        int bParents=findSet(b);
        if(aParents==bParents) return false;
        parents[bParents]=aParents; // b의 부모를 a의 부모로 바꾸기
        return true;
    }
    
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            V=Integer.parseInt(st.nextToken());
            E=Integer.parseInt(st.nextToken());
            parents=new int[V+1];
            long answer=0;
            int cnt=0;
 
            // 1. 자기자신을 부모로 설정 (초기설정)
            makeSet();
 
            // 2. 가중치 기준으로 오름차순으로 정렬
            ArrayList<Edge> array= new ArrayList<>();
            
            for (int i = 0; i < E; i++) {
                st=new StringTokenizer(br.readLine().trim());
                int A=Integer.parseInt(st.nextToken());
                int B=Integer.parseInt(st.nextToken());
                int C=Integer.parseInt(st.nextToken()); // 가중치
                array.add(new Edge(A,B,C));
                System.out.println(array);
            }
            Collections.sort(array);
            
            for (Edge edge : array) {
                int A=edge.from; int B= edge.to; int C=edge.weight;
                // 3. 사이클이 존재하지 않으면 간선 선택
                if(union(A,B)) {
                    answer+=C; // 가중치 더하기
                    if(++cnt==V-1) break;
                }
            }
            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.print(sb);
    }
}
/*

*/