[백준/BOJ] 1197번: 최소 스패닝 트리( Minimal Spanning Tree ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1197

 

풀이

이 문제는 그래프가 주어졌을 때, 그 그래프로부터 최소 신장 트리의 가중치 합을 출력하는 문제입니다.

 

여기서, 최소 신장 트리( Minimal Spanning Tree )는 주어진 그래프에서, 모든 정점을 지나는 트리 중에 가장 작은 가중치 합을 가진 트리를 말합니다.

 

이 최소 신장 트리를 구하는 알고리즘으로 Kruskal과 Prim 알고리즘이 있는데, 이 글에선 Kruskal 알고리즘을 사용했습니다.

이 알고리즘은 가중치가 작은 간선을 우선적으로 선택하여, 신장 트리를 구성하는 알고리즘입니다.

그 과정에서, 가중치를 기준으로 간선을 정렬해야 하고, 추가되는 간선이 순환 경로를 만드는지를 검사하는 기능이 필요합니다.

Kruskal 알고리즘에 대한 좀 더 자세한 내용은 여기에서 볼 수 있습니다.

[C++] Kruskal 알고리즘 ( 최소 신장 트리, MST 알고리즘 )

 

먼저, 주어진 데이터로부터 그래프를 구성합니다.

#define SIZE 10000	// 최대 정점의 개수

int parent[SIZE+1];	// 정점을 포함하는 집합

struct Edge{	
    int s, e, w;	// 정점 2개와 간선의 가중치

    Edge(int s, int e, int w){
        this->s = s;
        this->e = e;
        this->w = w;
    }
};

// main 함수 ----------------------------------------------------

int N = readInt();	// 정점의 개수
int M = readInt();	// 간선의 개수

for( int i = 0; i <= N; i++){	// 정점을 포함한 집합 초기화
    parent[i] = i;  // root 
}

vector<Edge> graph;

for( int i = 0; i < M; i++){
    int a = readInt();
    int b = readInt();
    int w = readInt();

    graph.emplace_back(a,b,w);	// 그래프 구성
}

emplace_back 함수는 Edge를 구성하는데 필요한 데이터만을 가지고, 내부적으로 Edge를 추가하는 함수입니다.

이 함수는 인자의 복사나 이동 과정이 필요 없기 때문에, 성능 향상을 가져올 수 있습니다.

좀 더 자세한 내용은 여기에서 볼 수 있습니다.

[C++] STL emplace 함수 설명 및 사용법

 

이제, Kruskal 알고리즘을 적용합니다.

bool compare( const Edge& e1, const Edge& e2){
    return e1.w < e2.w;
}

// main 함수 ----------------------------------------------------------
sort( graph.begin(), graph.end(), compare); // 가중치를 오름차순으로 정렬

int nTotalWeight = 0;

// 가중치가 작은 간선부터 트리 구성이 가능한지 검사
for( const Edge& x : graph){
    
    // 간선의 정점들이 이미 같은 집합에 속하면, 
    // 이제 이 간선은 순환 경로를 생성하므로 트리에서 제외해야 합니다.
    if (Find_Root(x.s) != Find_Root(x.e)){
        
        nTotalWeight += x.w;    // 간선이 MST에 포함되면 가중치 증가
        
        Union(x.s, x.e);
    }
}

cout << nTotalWeight;   // MST의 가중치 출력

 

Kruskal 알고리즘은 간선을 추가할 때, 간선의 두 정점이 같은 집합에 속하는지를 판단해야 합니다.

이때, 사용하는 알고리즘이 Union-Find 알고리즘입니다.

// Union-Find 알고리즘
int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}

이 함수들을 사용해서, 간선의 두 정점이 이미 같은 집합에 있으면, 이 간선이 순환 경로를 만드는 것을 알 수 있습니다.

반대로, 같은 집합에 없으면, 간선을 신장 트리에 포함하고, 이 두 정점이 속한 집합들을 결합합니다.

 

Union-Find에 관한 자세한 내용은 여기서 볼 수 있습니다.

 

마지막으로, 최소 신장 트리의 가중치 합을 출력하면 문제해결입니다.

 

소스 코드

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

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE 10000

int parent[SIZE+1];

struct Edge{
    int s, e, w;

    Edge(int s, int e, int w){
        this->s = s;
        this->e = e;
        this->w = w;
    }
};

bool compare( const Edge& e1, const Edge& e2){
    return e1.w < e2.w;
}

int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}

int main(){

    int N = readInt();
    int M = readInt();

    for( int i = 0; i <= N; i++){
        parent[i] = i;  // root 
    }

    vector<Edge> graph;

    for( int i = 0; i < M; i++){
        int a = readInt();
        int b = readInt();
        int w = readInt();

        graph.emplace_back(a,b,w);
    }

    sort( graph.begin(), graph.end(), compare); // 가중치를 오름차순으로 정렬

    int nTotalWeight = 0;

    for( const Edge& x : graph){
        
        // 간선의 정점이 같은 집합에 속하면, 순환 경로를 생성
        if (Find_Root(x.s) != Find_Root(x.e)){
            
            nTotalWeight += x.w;    // MST에 간선 추가
            
            Union(x.s, x.e);
        }
    }

    cout << nTotalWeight;   // MST의 가중치 출력

    return 0;
}