글 읽기 - 최소 스패닝 트리 메모리초과...

specialjin1 6년 전 0

메모리 초과가 나는데.. n*n 배열로 한게 문제가 되는건지 모르겠네요.. 아무리 생각해봐도

메모리를 줄일 방법이 생각나지 않습니다..ㅠ

#include <iostream>
using namespace std;
struct Edge {
	int A;
	int B;
	int C;
};
int **vertax;
int n,k,i,j,check_flag=0,weight=0;
Edge *edge;

int check_graph(int start,int now_edge,int pr_edge)
{	// graph인지 확인
	int check_count=0;
	if(now_edge == start) {
		check_flag=1;
		return 1;
	}
	if(check_flag==1) return 0;
	int i;
	for(i=0;i<n;i++)
	{
		if(vertax[now_edge][i]==1 && i!=pr_edge)
		{
			check_count += check_graph(start,i,now_edge);
		}
	}
	return check_count;
}
void quicksort(Edge a[], int first, int end)
{	// edge들을 가중치 오름차순으로 정렬
	int i=first, j=end;
	Edge h;
	int x = a[(first+end)/2].C;

	do {
		while(a[i].C<x) i++;
		while(a[j].C>x) j--;
		if(i<=j) {
			h=a[i];
			a[i]=a[j];
			a[j]=h;
			i++;
			j--;
		}
	} while(i<=j);
	if(first<end) quicksort(a,first,j);
	if(i<end) quicksort(a,i,end);
}
int kruskal()
{
	int i,j;
	for(i=0;i<k;i++)
	{
		vertax[edge[i].A-1][edge[i].B-1]=1;	// 연결
		vertax[edge[i].B-1][edge[i].A-1]=1;
		if(check_graph(edge[i].A-1,edge[i].B-1,edge[i].A-1)>0)
		{	// 연결시 graph가 나온다면 취소
			vertax[edge[i].A-1][edge[i].B-1]=0;
			vertax[edge[i].B-1][edge[i].A-1]=0;
		}
		else	// graph가 생성되지 않으면 가중치를 더하고 연결을 유지
			weight += edge[i].C;
		check_flag=0;
	}
	return weight;
}
int main(void)
{
	cin >> n >> k;
	edge = new Edge[k];
	vertax = new int*[n];
	for(i=0;i<n;i++) {
		vertax[i] = new int[n];
		for(j=0;j<n;j++)
			vertax[i][j] = 0;
	}
	for(i=0;i<k;i++) {
		cin >> edge[i].A >> edge[i].B >> edge[i].C;
	}
	quicksort(edge,0,k-1);
	cout << kruskal();
	for(i=0;i<n;i++)
		delete[] vertax[i];
	delete[] vertax;
	delete [] edge;
	return 0;
}