소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <string.h>
#define TRUE 1 /* 지나간 경로 표시 */
#define FALSE 0 /* 지나가지 않은 경로 표시 */
 
#define VERTICES 1001 /* 최대 정점의 수 */
#define INF 1000L /* 정점이 다른 정점과 연결되어 있지 않을 경우 무대한 값으로 표시 */
 
int adj_mat[VERTICES][VERTICES]; /* 정점의 위치 저장 배열 */
int selected[VERTICES]; /* 정점의 방문 표시 배열 */
int dist[VERTICES]; /* 간선의 최소값을 저장하기 위한 배열 */
 
/* 최소 가중치 값을 갖는 정점을 반환하는 함수  */
int get_min_vertex(int n)
{
    int V = 0;
 
    /*  */
    for (int count = 0; count < n; count++)
    { if (!selected[count]) { V = count; break; } }
 
    /*  */
    for (int count = 0; count < n; count++)
    { if (!selected[count] && (dist[count] < dist[V])) { V = count; } }
 
    return V;
}
 
/* Prim Algorithm */
int prim(int s, int n) /* S - 정점 배열의 시작점 위치, N - 배열의 크기 */
{
    /* Integer */
    int U = 0, Min = 0;
    /* U - 방문한 정점을 표시하는 변수, Min - 간선들의 최소거리들의 합을 나타내는 변수 */
 
    /* 가중치 배열을 초기화 하는 반복문 */
    for (int count = 0; count < n; count++) { dist[count] = INF; }
    
    /* 시작노드 선택 */
    dist[s] = 0;
    for (int count = 0; count <= n; count++)
    {
        /* 최소 가중치 값을 갖는 정점을 반환하는 함수 */
        U = get_min_vertex(count);
        /* 지나간 경로 표시 */
        selected[U] = TRUE; 
 
        /* 가중치 값 저장 배열에서 Dist[U] 원소가 가중치가 없는 경우 종료 */
        if (dist[U] == INF) { return 0; } 
 
        /* 최솟값 */
        Min += dist[U];
 
        for (int count = 0; count < n; count++) 
        {
            /* 간선의 가중치가 존재하는 경우 */
            if (adj_mat[U][count] != INF)
            {
                /* 간선의 거리를 확정 */
                if (!selected[count] && adj_mat[U][count] < dist[count]) { dist[count] = adj_mat[U][count]; }
            }
        }
    }
    /* 최솟값 반환 */
    return Min;
}
 
int main(void)
{
    /* Integer */
    unsigned int N = 0, M = 0; /* N - 정점의 개수, M - 간선의 개수 */
    unsigned int Temp[3] = { 0, 0, 0 }; 
 
    /* 초기화 */
    for (int ii = 0; ii < VERTICES; ii++) { for (int jj = 0; jj < VERTICES; jj++) { adj_mat[ii][jj] = INF; } } /* 정점 위치 값 배열 초기화 */
    memset(selected, FALSE, sizeof(selected)); /* 경로 표시 배열 초기화 */
 
    /* 정점 개수 입력 */
    scanf("%d", &N);
    /* 간선 개수 입력 */
    scanf("%d", &M);
    for (int count = 0; count < M; count++)
    {
        scanf("%d %d %d", &Temp[0], &Temp[1], &Temp[2]);
        adj_mat[Temp[0]-1][Temp[1]-1] = adj_mat[Temp[1]-1][Temp[0]-1] = Temp[2];
    }
 
    /* Prim Algorithm */
    printf("%d\n", prim(0, N));
 
    return 0;
}
cs



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

이 문제 이렇게 푸는 거 아닌감 ㅠㅠ;;;

도와주셈 ㅠㅠ