BOJ (C/C++, Java) 1647번: 도시 분할 계획

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

---

풀이

크루스칼 알고리즘을 이용했다.

대신 마지막에 연결되는 간선을 제외해 두 마을로 나누면서 가장 큰 연결 간선을 제외한다.

---

C/C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

int N, M;
vector<int> parents;
int lineCount = 0;
int totalCost = 0;

void unionNodes(int a, int b) {
    parents[b] = a;
}

int find(int a) {
    if (a == parents[a]) {
        return a;
    }
    return parents[a] = find(parents[a]);
}

int main() {
    // input
    scanf("%d %d", &N, &M);

    priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;

    for (int i = 0; i < M; i++) {
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        pq.push({cost, start, end}); // Note: cost first for priority_queue
    }

    // init
    parents.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        parents[i] = i;
    }

    // Kruskal's Algorithm
    while (lineCount < N - 2) {
        vector<int> edge = pq.top();
        pq.pop();
        int cost = edge[0], a = edge[1], b = edge[2];
        int p1 = find(a), p2 = find(b);

        if (p1 != p2) {
            unionNodes(p1, p2);
            totalCost += cost;
            lineCount++;
        }
    }

    // output
    printf("%d\n", totalCost);

    return 0;
}

 

Java 코드

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

public class Main {
    private static int N, M;
    private static int[] parents;
    private static int lineCount = 0;
    private static int totalCost = 0;

    private static void union(int a, int b) {
        parents[b] = a;
    }

    private static int find(int a) {
        if (a == parents[a])
            return a;
        return parents[a] = find(parents[a]);
    }

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bf.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2]-b[2]);
        for (int i = 0; i < M; i++) {
            String[] tmp = bf.readLine().split(" ");
            int start = Integer.parseInt(tmp[0]);
            int end = Integer.parseInt(tmp[1]);
            int cost = Integer.parseInt(tmp[2]);

            pq.add(new int[]{start, end, cost});
        }

        // init
        parents = new int[N + 1];
        for (int i = 1; i <= N; i++)
            parents[i] = i;

        //
        while (lineCount < N - 2) {
            int[] poll = pq.poll();
            int a = poll[0], b = poll[1], cost = poll[2];
            int p1 = find(a), p2 = find(b);
            if (p1 != p2) {
                union(p1, p2);
                totalCost += cost;
                lineCount++;
            }
        }

        System.out.println(totalCost);
    }
}