[Gold IV] 도시 분할 계획 - 1647

time

18분

Algorithm

• 최소 스패닝 트리 (MST)
• 크루스칼 알고리즘 (Kruskal's Algorithm)
• 유니온 파인드 (Union-Find)

Time Complexity

$O(M \log M)$

Logic

1. 모든 간선을 가중치 오름차순으로 정렬합니다.

Edge[] edges = new Edge[M];
// ... 간선 입력 ...
Arrays.sort(edges);

2. 유니온 파인드를 초기화합니다. 각 노드의 부모를 자기 자신으로 설정합니다.

parent = new int[N + 1];
for (int i = 0; i <= N; i++) parent[i] = i;

3. 크루스칼 알고리즘을 수행합니다. 가중치가 작은 간선부터 선택하며, 사이클이 발생하지 않는 경우에만 간선을 추가합니다. MST를 구성하면서 가장 큰 가중치를 기록합니다.

for (Edge edge : edges) {
    int rootA = UnionFind(edge.A);
    int rootB = UnionFind(edge.B);
    
    if (rootA == rootB) continue; // 사이클 발생
    
    parent[rootA] = rootB;
    sum += edge.C;
    maxC = Math.max(maxC, edge.C); // 가장 큰 가중치 기록
    cnt++;
    
    if (cnt == N - 1) break; // MST 완성
}

4. 유니온 파인드 함수로 노드의 루트를 찾습니다. 경로 압축을 통해 효율성을 높입니다.

static int UnionFind(int x) {
    if (parent[x] == x) return x;
    return parent[x] = UnionFind(parent[x]); // 경로 압축
}

5. MST의 총 가중치에서 가장 큰 가중치를 빼서 출력합니다. 이렇게 하면 두 개의 도시로 분할되며 최소 비용을 유지할 수 있습니다.

System.out.println(sum - maxC);

Review

• 두 개의 도시로 분할해야 하기 때문에 만들어진 MST에서 가장 가중치가 큰 간선을 제거했다.

Link

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