c언어 6497번 전력난 (백준)

#include <stdio.h>
#include <stdlib.h>

void sub(int n, int m);

typedef struct Node{ //간선을 담을 구조체
	int x;
	int y;
	int v;
}Node;

void shell(Node v[], int m) { //shell 정렬
	int i, j, gap = m/2;
	Node key;
	
	while(1) {
		if(gap%2 == 0) gap++;
		for(i=gap; i<m; i++) {
			key = v[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.v < v[j].v) v[j+gap] = v[j];
				else break;
			}
			v[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
}

int find(int p[], int x) { //노드가 속한 부분집합의 대표 노드 찾기
	if(p[x] == x) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) {//두 노드의 부분집합 합치기
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y;
}

int main(void) { 
	while(1) {
	int n, m; //n, m입력
	scanf("%d %d", &n, &m);
	if(!n && !m) break;
	sub(n, m);
	} return 0;
}

void sub(int n, int m) {
	int ans = 0, sum = 0; //ans : MST의 가중치의 합, sum : 모든 간선의 가중치의 합
	int *p = (int*) malloc(sizeof(int) * (n+1)); //메모리 동적 할당
	Node *v = (Node*) malloc(sizeof(Node) * (m+1));
	for(int i=0; i<=n; i++) p[i] = i; 
	for(int i=0; i<m; i++) scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].v); //간선입력
	
	shell(v, m);
	
	for(int i=0; i<m; i++) { //Krustal 알고리즘
		sum += v[i].v;
		if(find(p, v[i].x) != find(p, v[i].y)) {
			ans += v[i].v;
			merge(p, v[i].x, v[i].y);
		}
	}
	printf("%d\n", sum-ans); //절약한 금액을 구할 수 있다.
    free(p); //메모리 해제
    free(v);
    return;
}

풀이 : Krustal 알고리즘

1. n, m입력 받기

2. 노드가 속한 부분집합의 대표노드를 담을 공간과, 간선을 담을 구조체의 공간을 동적 할당합니다.

3. 노드가 속한 부분집합의 대표노드를 담을 공간은, 처음엔 자기자신을 대표노드로 해 줍니다.

4. 간선을 입력 받습니다.

5. shell sort (간선을)

6. Krustal 알고리즘을 통해, MST의 최소 가중치의 합을 구합니다.

7. 전체 간선의 가중치 - MST의 최소 가중치의 합 = 절약한 금액 을 출력한다.

8. 동적 메모리를 해제한다.

 

 

처음엔 동적할당을 안하고, n, m을 입력받으면, 자동메모리할당을 기대하며, 배열로 만들었는데, 테스트케이스가 여러개 일 때 자동메모리할당이 되지 않은 것 같아서 (런타임 에러가 떳습니다) 동적 할당으로 바꾸었습니다.

 

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

6497번: 전력난