[ 그래프 ] 최소 신장 트리(MST, 백준 1197)

 최소 신장 트리(MST)

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없다. -> 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.
• 최소 신장 트리 대표 알고리즘 : 크루스칼, 프림

 

💡 최소 신장 트리의 핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기

데이터를 노드가 아닌 에지 중심으로 저장한다. 그래서 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.

유니온 파인드 리스트도 함께 초기화한다. 자신의 인덱스 값으로 초기화한다.

 

 

2. 그래프 데이터를 가중치 기준으로 정렬한다.

에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

 

 

3. 가중치가 낮은 에지부터 연결 시도하기

가중치가 낮은 에지부터 연결을 시도한다.

이때 바로 연결하지 않고 이 에지를 연결햇을 때 사이클 형성 여부를 find()연산으로 확인한다. -> 대표노드가 같다면 사이클이 생기는 것

사이클 형성이 되지 않는 것을 확인하면 union()연산을 실행해 두 노드를 연결한다.

 

 

4. 연결한 에지의 갯수가 N-1개가 될 때까지 과정3 반복하기 

 

 1197 : 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

입력	출력
3 3 1 2 1 2 3 2 1 3 3	3

 

문제 풀이

• 오느래교훈 : 에지와 간선 헷갈리지말자!....에지만큼 반복해야되는데 간선만큼 반복하고 있었음..ㅋㅋ 
  다 푼 문제도 다시보자 👀

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1197_MST {
    static int V, E;
    static long[][] GraphEdge; //에지 정보 저장
    static long[] parent; //유니온 파인드 저장
    static long cost = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); //노드
        E = Integer.parseInt(st.nextToken()); //간선
        parent = new long[V+1];

        // parent 배열 초기화
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        // 에지 정보 입력
        GraphEdge = new long[E][3];
        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            GraphEdge[i][0] = Integer.parseInt(st.nextToken()); //노드 1
            GraphEdge[i][1] = Integer.parseInt(st.nextToken()); //노드 2
            GraphEdge[i][2] = Integer.parseInt(st.nextToken()); //가중치
        }
        //가중치를 기준으로 오름차순 정렬
        Arrays.sort(GraphEdge, (a, b) -> Long.compare(a[2], b[2]));

        Kruskal();

        System.out.println(cost);

    }

    private static void Kruskal() {
        int node = 0;
        for(int i=0;i<E;i++){
            if(node==V-1){
                break;
            }
            long n1 = find(GraphEdge[i][0]); 
            long n2 = find(GraphEdge[i][1]);
            if(n1!=n2){
                union((int) GraphEdge[i][0], (int) GraphEdge[i][1]);
                cost+=GraphEdge[i][2];
                node++;
            }
        }
    }

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

    private static void union(int i, int j) {
        long iRoot = find(i);
        long jRoot = find(j);
        if(iRoot!=jRoot) parent[(int) iRoot]=jRoot;
    }
}

 

 

크루스칼말고 프림도 푸러봐야지