(백준 1647번 도시 분할 계획) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)

최단 거리 찾는 알고리즘 3인방을 끝내고 오늘은 최소 스패닝 트리를 구하는 알고리즘에 대해 알아보았다. 라이님 블로그에 나온 알고리즘은 바로 크루스칼 알고리즘!

 

정렬 + 유니온 파인드를 이용하면 시간복잡도 O(ElogE)로 구할 수 있다!

 

gpt에게 살짝 수정시킨 알고리즘은 다음과 같다. 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator < (const Edge& other) const {
        return w < other.w;
    }
};

int uf[1000];

int find(int a) {
    if (uf[a] < 0) return a;
    return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    uf[b] = a;
    return true;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<Edge> edges;
    edges.reserve(M); // 메모리 할당 최적화

    for (int i = 0; i < M; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back({a - 1, b - 1, c});
    }

    // 간선 정렬
    sort(edges.begin(), edges.end());

    int result = 0, cnt = 0;
    fill(uf, uf + N, -1);
    for (const auto& e : edges) {
        if (merge(e.u, e.v)) {
            result += e.w;
            if (++cnt == N - 1) break; // 모든 노드를 연결했다면 종료
        }
    }

    printf("%d\n", result);
    return 0;
}

 

위 풀이를 기준으로 1647번을 풀어보았다.

 

백준 1647번

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

 

MST를 먼저 구한 다음 가장 가중치가 큰 간선을 잘라주면 하나의 트리가 두 개의 트리로 나눠진다.

이미 간선들은 크기에 따라 정렬되어 있으므로 마지막 간선의 크기만 저장했다가  MST 가중치 합에서 빼주면 된다!

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
	int u, v, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

int uf[100000];

int find(int a) {
	if (uf[a] < 0) return a;
	return uf[a] = find(uf[a]);
}

int merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[b] = a;
	return true;
}
int main() {
	int N, M; scanf("%d %d", &N, &M);
	vector<Edge> edges;
	edges.resize(M);
	for (int i = 0; i < M; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		edges[i] = { u - 1, v - 1, w };
	}
	fill(uf, uf + N, -1);
	sort(edges.begin(), edges.end());

	int result = 0, cnt = 0, max_len = 0;
	for (Edge& e : edges) {
		if (merge(e.u, e.v)) {
			result += e.w;
			if (++cnt == N - 1) {
				max_len = e.w;
				break;
			}
		}
	}

	printf("%d", result - max_len);
	return 0;
}