백준 1647 - 도시 분할 계획

문제

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

리뷰

문제에서는 주어진 간선들중 일부를 택하여 마을을 두 개로 분리하는데
이 때 채택한 간선들의 합이 최소가 되는 것을 요구하고 있다.

크루스칼 알고리즘

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

크루스칼 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree, MST)를
구하는데 사용되는 알고리즘이다. MST란 그래프 내의 모든 정점을 연결하면서 사이클을
만들지 않는 부분 그래프 중에서 간선의 가중치 합이 최소인 트리를 의미한다.

크루스칼 알고리즘은 일반적으로 다음 순서로 동작한다.
1. 모든 간선을 가중치 순으로 오름차순 정렬한다.
아래 로직에서는 최소힙을 활용하여 간선을 저장했다. 크루스칼에 사용하였다.
2. 정렬된 간선 리스트에서 가중치가 가장 작은 간선부터 선택한다.
3. 선택된 간선의 양 끝 정점이 서로 다른 집합에 속한다면(사이클을 형성하지 않는다면)
해당 간선을 MST에 추가한다. 이때 두 정점을 같은 집합에 속하게 한다.
4. 위 과정을 $N-1$개의 간선을 채택할 때까지 반복한다.

기존의 최소 신장 트리를 형성하는 알고리즘들이 정점이 $N$개 주어졌을 때
$N-1$개의 간선을 채택하여 MST를 형성했던 것을 $N-2$개 간선을 채택하도록
변경해주면 자연스레 채택된 간선들의 합을 최소로 하며 마을 두 개로 분리할 수 있다.

로직의 시간복잡도는 크루스칼 알고리즘의 복잡도인 $O(MlogM)$로 수렴하고
간선의 개수가 최대인 $M$이 100만일때도 무난히 제한 조건인 2초를 통과한다.

참고
크루스칼 알고리즘을 구현하는데 있어 활용된 유니온 파인드 연산을
경로 압축과 균형 트리를 활용하여 더 최적화하였다.

https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-7511-%EC%86%8C%EC%85%9C-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%82%B9-%EC%96%B4%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int N;
    static int[] parent;
    static PriorityQueue<Edge> pq=new PriorityQueue<>(Comparator.comparingInt(edge->edge.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N= parseInt(st.nextToken());
        int M=parseInt(st.nextToken());

        while(M-->0){
            st=new StringTokenizer(br.readLine());
            int u=parseInt(st.nextToken());
            int v=parseInt(st.nextToken());
            int w=parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        System.out.println(kruskal());
        br.close();
    }

    static int kruskal(){ // O(M log M)
        parent=new int[N+1];
        Arrays.fill(parent, -1);

        int selectedEdge=0;
        int costSum=0;

        while(selectedEdge<N-2){
            Edge e = pq.poll(); // logM


            int r1 = find(e.u);
            int r2 = find(e.v);

            if(r1==r2) continue;

            if(parent[r1]<parent[r2]){
                parent[r1]+=parent[r2];
                parent[r2]=r1;
            }else{
                parent[r2]+=parent[r1];
                parent[r1]=r2;
            }

            costSum+=e.w;
            selectedEdge++;
        }

        return costSum;
    }

    static int find(int u){
        if(parent[u]<0) return u;

        return parent[u]=find(parent[u]);
    }


    static class Edge{
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과