Project Euler #107 (Minimal network)

차후에 자세하게 설명하겠지만 MST (Minimal Spanning Tree: 최소 신장 트리) 문제다.

여기서 "최소 신장 트리"라는 말은 "최소 가중치 신장 트리"라는 말의 단축형으로, 

모든 신장 트리는 정확하게 |V| - 1개의 간선을 가지게 된다. (아래 코드의 coo부분)

따라서 간선의 수를 최소화 할 수는 없다.

MST에 자세히 이후에 글을 쓰겠다. (https://en.wikipedia.org/wiki/Minimum_spanning_tree)

아래는 크루스칼 알고리즘으로 구현하였다. (크루스컬 알고리즘 의사코드 - 한글위키)

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

#define N 40

struct edge {
	int u, v, weight;
};

void swap(edge &e1, edge &e2) {
	edge t;
	t= e1;
	e1= e2;
	e2= t;
}

void sort(edge *arr, int size) {
	int i, j;
	for (i = 0; i < size; i++) {
		for (j = i + 1; j < size; j++) {
			if (arr[i].weight > arr[j].weight) {
				swap(arr[i], arr[j]);
			}
		}
	}
}

void main() {
	int i, j, n, u, v, coo, su, sv, set_no, weight, main_set;
	char line[300], *token;
	int setflag[N];
	edge *edges;
	int edges_count = 0, total_weight = 0, mst_sum = 0;
	FILE *input;

	input = fopen("p107_network.txt", "rt");
	//printf("input = %s\n", (input == NULL ? "NULL" : "OPENED"));
	j = 0;
	while (fscanf(input, "%s\n", line) != EOF) {
		token = strtok(line, ",");
		i = 0;
		while (token) {
			if (*token != '-' && i < j) edges_count++;
			token = strtok(NULL, ",");
			i++;
		}
		j++;
	}
	fseek(input, 0, SEEK_SET);

	edges = (edge*)malloc(sizeof(edge)*edges_count);
	n = 0;
	j = 0;
	while (fscanf(input, "%s\n", line) != EOF) {
		token = strtok(line, ",");
		i = 0;
		while (token) {
			if (*token != '-' && i < j) {
				edges[n].u = i;
				edges[n].v = j;
				edges[n].weight = atoi(token);
				total_weight += atoi(token);
				n++;
			}
			token = strtok(NULL, ",");
			i++;
		}
		j++;
	}

	sort(edges, edges_count);

	set_no = 0;
	for (i = 0; i < N; i++) setflag[i] = set_no++;

	coo = 0;
	for (n = 0; n < edges_count; n++) {
		u = edges[n].u;
		v = edges[n].v;
		weight = edges[n].weight;
		su = setflag[u];
		sv = setflag[v];
		if (su != sv) {
			coo++;
			mst_sum += weight;
			for (i = 0; i < N; i++) {
				if (setflag[i] == su || setflag[i] == sv) {
					setflag[i] = set_no;
				}
			}
			set_no++;

			if (coo == N - 1) break;
		}

	}

	printf("total_weight = %d, mst_weight = %d\n", total_weight, mst_sum);
	printf("max_saving = %d\n", total_weight - mst_sum);
	system("pause");
	fclose(input);
	free(edges);
}