차후에 자세하게 설명하겠지만 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); }
'Project Euler' 카테고리의 다른 글
Project Euler #103 (Special subset sums: optimum) (0) | 2016.09.09 |
---|---|
Project Euler #104 (Pandigital Fibonacci ends) (0) | 2016.09.09 |
Project Euler #102 (Triangle containment) (0) | 2016.09.07 |
Project Euler #101 (Optimum polynomial) (0) | 2016.09.05 |
Project Euler #1 (0) | 2014.10.28 |
댓글