최소 스패닝 트리(백준_1197)

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

문제 설명

그래프가 주어졌을 때, 최소 신장 트리를 구현하고 가중치의 합을 구하는 문제이다.

 

 

문제에 대한 아이디어

최소 신장 트리를 구현하는 문제이다. 최소 신장 트리를 구하는 대표적인 알고리즘인 크루스칼 알고리즘으로 이 문제를 풀었다.

크루스칼 알고리리즘은 O(|E|log|E|)안에 최소신장트리를 만들 수 있다.
왜냐 하면 모든 edge를 탐색하는데 O(E) 시간이 걸리고 간선을 오름차순으로 정렬하는데 걸리는 시간은 O(|E|log|E|) 이기 때문이다.

 

1. 에지 리스트를 입력 받고 가중치 순으로 정렬한다.

2. 작은 에지부터 탐색하면서 크루스칼 알고리즘을 실행한다.

Node s와 Node e를 Union-find 연산 중 각각 find를 실행하고 cycle이 아니면 union을 실행한다. 

이렇게 총 노드-1번 반복한다. 왜냐하면 모든 노드가 연결하는 edge의 수는 노드 갯수 - 1 이기 때문이다.

만약 cycle이면 다음 인덱스로 바로 넘어간다.

 

구현

• Edge

static class Edge implements Comparable<Edge>{
    private int a;
    private int b;
    private int c;
    public Edge(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override // 우선순위 큐에 넣을 때 가중치를 기준으로 함
    public int compareTo(Edge o) {
        return this.c- o.c;
    }
}

• Union

public static void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a==b) return;
    else arr[b] = a;

}

• Find

public static int find(int a){
    if(arr[a] == a) return a;
    else return arr[a] = find(arr[a]);
}

• Main

static int arr[];
public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    int v = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    //우선순위 큐 선언
    PriorityQueue<Edge> edges = new PriorityQueue<>();
    //정답 배열 만들기
    arr = new int[v+1];
    for(int i=1; i<v+1; ++i){
        arr[i] = i;
    }
    for(int i =0; i<e; ++i){
        st = new StringTokenizer(buf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        edges.add(new Edge(a,b,c));
    }
    int useEdge =0;
    int result=0;
    //크루스칼 알고리즘 시작
    while(useEdge < v-1) {
       Edge edge = edges.poll();
       if (find(edge.a) != find(edge.b)) { //사이클이 아니면 union
             union(edge.a, edge.b);
             result += edge.c;
             useEdge++;
       }
    }
    System.out.println(result);
}

 

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1197.java

GitHub - Heron-Woong/CodingTest_Practice