🙇‍♀️[Gold IV] 최소 스패닝 트리 - 1197

문제 링크

성능 요약

메모리: 4848 KB, 시간: 36 ms

분류

최소 스패닝 트리, 그래프 이론

제출 일자

2024년 2월 29일 15:44:28

문제 설명

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

🚀풀이

MST인 최소 스패닝 트리는 Kruskal 알고리즘을 통해서 풀 수 있다.

물론 Prim이나 다른것들도 가능함.

Kruskal을 사용하기 위해서 DisjointSet을 알아야한다.

Union & Find인데 루키스 강의를 생각하면 리니지 배틀그라운드 예시로 들었던 그 부분이다.

int unf[100001];

이걸로 자신의 대장이 누군지 저장한다.

찾는 함수

int Find(int v)
{
	if (v == unf[v])
		return v;
	return unf[v] = Find(unf[v]);
}

자신의 대장이 자기 자신이면 바로 자기를 뱉는다.
그게 아니면 재귀적으로 자신의 대장을 끝까지 쫒아가 찾는다.

합치는 함수

void Merge(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if (a != b)
		unf[a] = b;
}

각각 자신의 대장이 누구인지 찾는다.

만약 대장이 서로 다르다면 다른 그룹이란 뜻이므로 한쪽으로 이전 시켜준다.
위의 방식은 naive한 방식이다.
조금더 최적화하는 방법이 있지만 그냥 사용함.

위의 내용으로 문제를 해결한다.

먼저 정점을 하나의 구조체로 잡았다.

int v, e;

struct Edge
{
	int v1, v2, value;
	Edge(int a, int b, int c)
	{
		v1 = a;
		v2 = b;
		value = c;
	}

	bool operator<(const Edge& other) const
	{
		return value < other.value;
	}
};

solve함수는 아래와 같다.

주석으로 다 설명함.

강의 몇 번 보니 이해가 되더라.. ㅎ

void solve()
{
	vector<Edge> edges;
	cin >> v >> e;
	// 각 정점의 부모는 자기이다.
	for (int i = 1; i <= v; ++i)
		unf[i] = i;

	// 그래프 연결정보 입력
	int v1, v2, val;
	for (int i = 1; i <= e; ++i)
	{
		cin >> v1 >> v2 >> val;
		edges.push_back({ v1, v2, val });
	}

	// 비용을 기준으로 정렬하기
    // 그리디한 방법이다.
	sort(edges.begin(), edges.end());

	// Union & Find 를 이용한 Kruscal 알고리즘
	int res = 0; // 최소 비용을 계산
	for (int i = 0; i < e; ++i)
	{
		int fa = Find(edges[i].v1);
		int fb = Find(edges[i].v2);

		if (fa != fb)
		{
			res += edges[i].value;
			Merge(edges[i].v1, edges[i].v2);
		}
        // 대장이 같으면 사이클이 생긴다는 뜻이므로 넘긴다.
	}

	cout << res;
}

image

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int unf[100001];
int v, e;

struct Edge
{
	int v1, v2, value;
	Edge(int a, int b, int c)
	{
		v1 = a;
		v2 = b;
		value = c;
	}

	bool operator<(const Edge& other) const
	{
		return value < other.value;
	}
};

int Find(int v)
{
	if (v == unf[v])
		return v;
	return unf[v] = Find(unf[v]);
}

void Merge(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if (a != b)
		unf[a] = b;
}

void solve()
{
	vector<Edge> edges;
	cin >> v >> e;
	// 각 정점의 부모는 자기이다.
	for (int i = 1; i <= v; ++i)
		unf[i] = i;

	// 그래프 연결정보 입력
	int v1, v2, val;
	for (int i = 1; i <= e; ++i)
	{
		cin >> v1 >> v2 >> val;
		edges.push_back({ v1, v2, val });
	}

	// 비용을 기준으로 정렬하기
	sort(edges.begin(), edges.end());

	// Union & Find 를 이용한 Kruscal 알고리즘
	int res = 0;
	for (int i = 0; i < e; ++i)
	{
		int fa = Find(edges[i].v1);
		int fb = Find(edges[i].v2);

		if (fa != fb)
		{
			res += edges[i].value;
			Merge(edges[i].v1, edges[i].v2);
		}
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고