글 읽기 - 단순 크루스칼인줄알았는데 잘못 알고 있는걸까요?..

cjstjdgur123 5년 전 1

노드가 1개일 경우, 노드가 필요없으니 0

그 외에는 크루스칼로 해놨습니다. i, j 기록이 필요할줄알고 쓸데없이 구조체를 만들어뒀는데,

수정을 안해둬서 그대로 두었어요.

제가 놓친 부분이 무엇이 더 있을까요?.. ㅠㅠ

#include <stdio.h>
#include <stdlib.h>
#define llu unsigned long long

int n;

typedef struct {
    int value;
} Node;

int compare ( const void* a, const void* b )
{
    if( ((Node*)a)->value > ((Node*)b)->value )
        return 1;
    return 0;
}

int main ( void )
{
    scanf( "%d", &n );
    
    if( n == 1 )
    {
        scanf( "%d", &n );
        printf( "0" );
        return 0;
    }
    
    Node nodes[ n * (n - 1) / 2 ] = { 0 };
    int arr[ n ][ n ] = { 0 }, idx = 0;
    for( int y = 0; y < n; ++ y )
        for( int x = 0; x < n; ++ x )
            scanf( "%d", &arr[ x ][ y ] );
    for( int y = 1; y < n; ++ y )
        for( int x = 0; x < y; ++ x )
            nodes[ idx ].value = arr[ x ][ y ], idx++;
    qsort( nodes, idx, sizeof( Node ), compare );
    
    llu result = 0;
    for( int i = 0; i < n - 1; ++ i )
        result += nodes[ i ].value;
    printf( "%llu", result );
    
    /* for debug
    for( int i = 0; i < n*(n-1)/2; ++ i )
        printf( "\nNode: %d", nodes[ i ] );
    //*/
    
    return 0;
}

djm03178 5년 전 3

크루스칼 알고리즘을 잘못 알고 계시는 것 같습니다. 크루스칼 알고리즘은 "간선에 의해 2개의 서로 다른 트리가 하나로 합쳐지는 경우"에만 그 간선을 사용해야 하고 나머지의 경우에는 무시해야 하는데 이 코드에는 그러한 처리가 전혀 보이지 않네요.

cjstjdgur123 5년 전 0

아.. 감사합니다..

저게 맞다고 맹신하고 있어서 계속 헛걸음질만했네요..

다음부터 안풀릴땐 이런것도 확인해야겠어요 감사합니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

단순 크루스칼인줄알았는데 잘못 알고 있는걸까요?..

cjstjdgur123 5년 전 1

djm03178 5년 전 3

cjstjdgur123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말