[C/C++] 프로젝트 오일러 #107 Minimal Network(프림 알고리즘)

Project Euler 107번 문제는 네트워크의 최소 비용 연결에 관한 문제입니다. 주어진 그래프는 여러 개의 노드(점)와 그 노드를 연결하는 에지(선)로 이루어져 있습니다. 각 에지는 비용(가중치)을 가지고 있으며, 이 그래프는 모든 노드가 연결되어 있는 상태입니다. 즉, 어느 노드에서든 다른 노드로 이동할 수 있는 경로가 반드시 존재합니다.

문제의 목표는 주어진 그래프에서 가능한 최소 비용으로 모든 노드를 연결하는 것입니다. 이를 달성하기 위해 불필요한 에지를 제거해도 되며, 단 제거 후에도 모든 노드가 연결되어 있어야 합니다. 이러한 최소 비용의 네트워크는 ’최소 신장 트리(Minimum Spanning Tree, MST)’라고 불립니다.

문제를 해결하려면 다음과 같은 과정이 필요합니다. 먼저, 원래 그래프의 전체 가중치를 계산합니다. 이후 최소 신장 트리를 찾는 알고리즘(예: Kruskal 또는 Prim 알고리즘)을 사용해 MST를 구합니다. MST의 가중치를 계산한 뒤, 원래 그래프의 가중치에서 MST의 가중치를 뺀 값을 구하면 절감된 비용(savings)을 알 수 있습니다. 이 절감된 비용이 문제에서 구하고자 하는 최종 답입니다.

입력으로는 그래프가 주어지며, 이는 인접 행렬로 표현됩니다. 행렬의 각 셀에는 두 노드를 연결하는 에지의 가중치가 들어있고, 에지가 없는 경우 빈 칸 또는 “-“로 표시됩니다. 출력값은 MST를 사용해 절감된 비용입니다.

예를 들어, 네 노드로 이루어진 그래프가 있다고 가정합시다. 각 에지의 비용이 다음과 같다면:
• A와 B를 연결하는 에지의 비용은 5
• A와 C를 연결하는 에지의 비용은 10
• B와 C를 연결하는 에지의 비용은 15
• B와 D를 연결하는 에지의 비용은 20
• C와 D를 연결하는 에지의 비용은 25

원래 네트워크의 전체 가중치는 \( 5 + 10 + 15 + 20 + 25 = 75 \) 입니다. 최소 신장 트리를 구하면 다음과 같은 연결로 비용을 최소화할 수 있습니다:
• A와 B를 연결하는 에지(5)
• A와 C를 연결하는 에지(10)
• B와 D를 연결하는 에지(20)

MST의 가중치는 \( 5 + 10 + 20 = 35 \) 이며, 절감된 비용은 \( 75 - 35 = 40 \) 이 됩니다. 이를 통해 네트워크의 최소화된 비용과 절감을 확인할 수 있습니다.

이 문제는 그래프 이론의 기본적인 알고리즘을 사용해 효율적으로 해결하는 것을 목표로 하며, 프로그래밍적으로 구현해야 합니다.

 

Minumum Spanning Tree

 

제가 작성한 소스입니다.  알고리즘 공부를 하기 전에 짠 소스라 지금 보니 다소 문제가 있는 부분들이 있네요.

//------------------------------------------------
//    Project Euler #107 - Minimal Network
//        - by Aubrey Choi
//        - created at 2015-05-11
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

#define    FILENAME    "p107_network.txt"

int network[40][40];

int solve1()
{
    int sum = 0;
    unsigned nodes[40];
    char visited[40];
    memset(nodes, -1, sizeof(nodes));
    memset(visited, 0, sizeof(visited));
    nodes[0] = 0;
    while(true)
    {
        int r = -1, min = 10000;
        for( int i = 0 ; i < 40 ; i++ )
            if( visited[i] == 0 && nodes[i] < min ) { r = i; min = nodes[i]; }
        if( r == -1 ) break;
        sum += nodes[r];
        visited[r] = 1;
        for( int c = 0 ; c < 40 ; c++ )
        {
            if( network[r][c] == 0 ) continue;
            if( visited[c] ) continue;
            if( network[r][c] < nodes[c] ) nodes[c] = network[r][c];
        }
    }
    return sum;
}

int main()
{
    FILE *fi = fopen(FILENAME, "r");

    int total = 0;
    for( int r = 0 ; r < 40 ; r++ )
    {
        char str[1000];
        fgets(str, 1000, fi);
        int c = 0;
        for( char *p = strtok(str, " ,\r\n\t"); p ; p = strtok(0, " ,\r\n\t"))
        {
            int t = (*p == '-')?0:atoi(p);
            network[r][c++] = t;
            total += t;
        }
    }
    fclose(fi);
    total /= 2;

    printf("ans = %d\n", total - solve1());

    return 0;
}

 

이 코드는 Project Euler #107 - Minimal Network 문제를 해결하기 위한 프로그램입니다. 주요 아이디어는 주어진 네트워크의 전체 비용을 계산하고, 최소 신장 트리(Minimum Spanning Tree, MST)의 비용을 구한 뒤, 두 값의 차이를 출력하여 절감된 비용을 구하는 것입니다. 코드의 각 부분을 설명하겠습니다.

1. #define과 전역 변수

• FILENAME은 네트워크 데이터가 저장된 파일 이름입니다. 프로그램은 이 파일에서 데이터를 읽습니다.
• network[40][40]은 네트워크의 인접 행렬을 저장하는 2차원 배열입니다. 행렬의 각 원소는 노드 간 에지의 가중치를 나타냅니다.

2. solve1() 함수

이 함수는 Prim 알고리즘을 사용하여 최소 신장 트리(MST)의 비용을 계산합니다.
• 초기화:
• nodes[40]: 각 노드가 MST에 포함되기 위해 필요한 최소 비용을 저장합니다. -1로 초기화되지만 실제로는 모든 비트를 1로 설정한 상태입니다(즉, 매우 큰 값으로 초기화).
• visited[40]: MST에 포함된 노드 여부를 나타냅니다. 초기값은 모두 0(방문하지 않음)입니다.
• nodes[0] = 0: 첫 번째 노드는 비용 없이 MST에 포함됩니다.
• 알고리즘 루프:
• 가장 작은 비용으로 MST에 추가되지 않은 노드를 찾습니다.
• r는 선택된 노드, min은 최소 비용입니다.
• sum에 해당 노드의 비용을 추가합니다.
• 선택된 노드를 방문 처리(visited[r] = 1)하고, 그 노드와 연결된 다른 노드들의 비용을 갱신합니다.
• 아직 MST에 포함되지 않은 노드(visited[c] == 0)만 갱신합니다.
• nodes[c] 값은 network[r][c]와 기존 값 중 더 작은 값으로 갱신됩니다.
• MST 구성 완료:
• 더 이상 방문할 노드가 없으면 루프를 종료하고, sum을 반환합니다. 이 값이 MST의 총 비용입니다.

3. main() 함수

이 함수는 프로그램의 진입점으로, 다음 작업을 수행합니다.
1. 파일 읽기:
• fopen()으로 FILENAME에 저장된 네트워크 데이터를 엽니다.
• 각 줄(fgets())을 읽어와서 노드 간의 가중치를 network 배열에 저장합니다.
• -로 표시된 값은 연결이 없음을 나타내며, 이 경우 network[r][c]에 0을 저장합니다.
• total은 네트워크 전체의 비용 합계를 계산합니다. 모든 가중치를 더한 뒤, 방향성이 없는 그래프이므로 2로 나눕니다.
2. MST 비용 계산 및 절감 비용 출력:
• solve1()을 호출하여 MST의 비용을 계산합니다.
• 네트워크의 전체 비용(total)에서 MST의 비용을 뺀 값을 출력합니다.
3. 종료:
• 파일을 닫고 프로그램을 종료합니다.

Prim 알고리즘을 사용하는 이유

Prim 알고리즘은 그래프의 MST를 구하는 효율적인 방법 중 하나로, 주어진 네트워크를 항상 연결 상태로 유지하면서 가장 적은 비용으로 확장합니다. 이 문제에서는 적합한 선택입니다.