[백준] 1197번 : 최소 스패닝 트리 (Minimum Spanning Tree)

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

1197번: 최소 스패닝 트리

문제 :

주어진 정점과 간선의 정보를 토대로 그래프의 mst 가중치를 구하는 문제였다. 이 문제를 해결하기 위해서 신경 써 줘야 하는 지점이 두 군데 있었다.

 

1. 정점의 개수가 10000개이다.

 

2차원 배열을 통한 가중치 그래프의 구현은 10000*10000*4byte = 400 mb 를 차지하기 때문에 문제에서 허용하는 메모리(128mb)를 초과한다. 따라서 그래프를 구현하기 위한 더 효율적인 자료구조가 필요했고, 이를 찾아보는 과정에서 pair라는 c++ stl에 대해 알아보게 되었다. pair을 처음 접해보면서 https://sarah950716.tistory.com/4 이 블로그에서 간단하게만 사용법을 알아보고, vector< pair <int, int> > graph [ ]의 형식으로 그래프를 구현해줌으로써 필요한 메모리를 줄일 수 있었다.

 

2. 최소 스패닝 트리의 가중치는 -2147483648 보다 크거나 같고, 2147483647 보다 작거나 같다.

 

이 부분을 얼핏보고 가중치가 4byte int 내에서 처리 가능한 값이라고 생각했지만, dist [] 배열을 연산하는 과정에서 overflow 가 발생할 가능성이 있기에 자료형을 바꾸어 주어야 했다. 모든 dist의 값은 절댓값이 100만을 넘기지 않는 4byte 안에 충분히 들어가는 값이므로 마지막에 dist배열을 더한 값을 저장할 변수만 long long int로 선언해주면서 문제를 해결할 수 있었다.

문제 해결:

#include <iostream>
#include <vector>
#include <utility>
#define MAX 10001
#define INFI 987654321
using namespace std;

//first : connected vertex , second: connect weight
vector <pair<int,int>> graph[MAX];

// V: 정점의 개수 , E: 간선의 개수
int V, E;

//이하는 prim 알고리즘에 사용되는 배열
int dist[MAX];
bool visited[MAX];


//prim 알고리즘이 끝난 후 최종적으로 저장되어있는 dist에 있는 가중치들을 합한 값을 반환
int getWeightSum()
{
	long long int ret = 0;
	for(int i=1; i<=V; i++)
	{
		ret += dist[i];
	}
	return ret;
}

//dist 배열에서 가장 작은 값의 인덱스를 반환
int extractMin()
{
	int min=INFI, index;
	for(int i=1; i<=V; i++)
	{
		if(dist[i] < min && !visited[i])
		{
			min = dist[i];
			index = i;
		}
	}
	return index;
}


//mst 계산
void prim()
{
	//dist를 초기화
	for(int i=1; i<=V; i++)
	{
		dist[i] = INFI; 
	}
	
	//시작점은 1 (임의의 값임)
	dist[1] = 0;
	
	for(int i=0; i<V; i++)
	{
		int u = extractMin();
		visited[u] = true;
		for(int j=0; j<graph[u].size(); j++)
		{
			int cVertex = graph[u][j].first;
			int weight = graph[u][j].second;
			if(!visited[cVertex] && weight < dist[cVertex])
			{
				dist[cVertex] = weight;
			}
		}
	}
	
}


//초기화 함수
void init()
{
	int a,b,c;
	cin >> V >> E;
	for(int i=0; i<E; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b,c));
		graph[b].push_back(make_pair(a,c));
	}
}

int main() {
	init();
	prim();
	cout << getWeightSum();
	return 0;
}

 

아쉬운점

1. 단순히 변수를 잘못쓴 이유로 ( i 루프 안에 i를 또 씀,  j가 들어가야 할 위치에 i를 넣음) 쓸데없이 디버깅 시간이 길어졌다.  i j 와 같은 변수를 쓸때는 더욱 더 신중하게 하고, 디버깅시 유심히 확인해야 할 것 같다.

2. dist 값을 heap 으로 유지한다면 시간복잡도를 더 줄일 수 있었다. mst 알고리즘들이 더욱 익숙해지면 시간복잡도를 더 줄이는 방법으로도 문제를 해결해봐야 한다.