남극기지 문제 관련해서 질문 있습니다!(코드있습니다)

  • pikakr
    pikakr

    최소신장 트리를 활용해서 결과값을 도출하려고 하는데

    무엇이 잘못됬는지 잘 이해가 가지 않습니다

    거리순으로 정렬을 하고,

    0부터 시작해서 최소신장트리를 구축한 후

    가장 큰 값을 3번쨰 자리 소수점을 반올림 한 후 출력했으나

    샘플 예제는 잘 작동하지만 오답이 나옵니다

    #include
    #include
    #include
    #include

    #define MAXSIZE 150
    #define INT_MAX 210000000
    #define INFINITE INT_MAX

    using namespace std;

    struct AXIS
    {
    double xPos;
    double yPos;
    };

    struct DistanceTerm
    {
    int fromIndex;
    int toIndex;
    double distance;
    };

    void InitVariable();
    void GetDataFromUser( AXIS* artic, int numOfArtic );
    void SetLengthTableData( AXIS *artic, int numOfAtic );
    double Distance( AXIS& first, AXIS& second );
    void PrintAnswerByMST( int numOfArtic );

    bool compare( DistanceTerm first, DistanceTerm second )
    {
    if( first.distance < second.distance )
    return true;

    return false;

    }

    double g_ArticLength[ MAXSIZE ][ MAXSIZE ];
    DistanceTerm g_DistanceTerm[ MAXSIZE * MAXSIZE ];
    int g_MSTTableInex = 0;
    int main()
    {
    int numOfCase = 0;
    int tryOfCase = 0;

    AXIS artic[ MAXSIZE ];
    cin >> numOfCase;
    
    while( tryOfCase != numOfCase )
    {
        int numOfArtic = 0;
    
    
        cin >> numOfArtic;
    
        InitVariable(); 
        GetDataFromUser( artic, numOfArtic );
        SetLengthTableData( artic, numOfArtic );
        PrintAnswerByMST( numOfArtic );
    
        tryOfCase++;
    }

    }

    void InitVariable()
    {
    for( int i = 0 ; i < MAXSIZE; i++ )
    for( int j = 0 ; j < MAXSIZE; j++ )
    {
    g_ArticLength[ i ][ j ] = INFINITE;
    }

    g_MSTTableInex = 0;

    }

    void GetDataFromUser( AXIS* artic, int numOfArtic )
    {

    int curPositionIndex = 0;
    
        while( curPositionIndex != numOfArtic )
        {
            cin >> artic[ curPositionIndex ].xPos >> artic[ curPositionIndex ].yPos;
            curPositionIndex++;
        }

    }

    double Distance( AXIS& first, AXIS& second )
    {
    return sqrt( pow( first.xPos - second.xPos, 2 ) +
    pow( first.yPos - second.yPos, 2 ) );
    }

    void SetLengthTableData( AXIS *artic, int numOfArtic )
    {
    int termIndex = 0;

    for( int i = 0 ; i < numOfArtic; i++ )
            for( int j  = 0 ; j < numOfArtic; j++ )
            {
        //      g_ArticLength[ i ][ j ] = g_ArticLength[ j ][ i ] = Distance( artic[ i ], artic[ j ] );
                if( i != j )
                {
                    g_DistanceTerm[ g_MSTTableInex ].fromIndex = i;
                    g_DistanceTerm[ g_MSTTableInex ].toIndex = j;
                    g_DistanceTerm[ g_MSTTableInex ].distance = Distance( artic[ i ], artic[ j ] );
                    g_MSTTableInex++;
                }
            }
    
        sort( g_DistanceTerm, g_DistanceTerm + g_MSTTableInex , compare );
    
    //  for( int i = 0 ; i <  g_MSTTableInex  ; i++ )
        //  cout << g_DistanceTerm[ i ].fromIndex <<" " << g_DistanceTerm[ i ].toIndex << " " <<g_DistanceTerm[ i ].distance << endl;

    }

    int FindNextNode( bool *visited, int sPos, int numOfArtic )
    {
    int nextNode = 0;
    int minValue = INFINITE;

    for( int i = 0 ; i < g_MSTTableInex ; i++ )
    {
        if( ( sPos == g_DistanceTerm[ i ].fromIndex ) && (!visited[ g_DistanceTerm[i].toIndex ] ) )
        {
            if( minValue > g_DistanceTerm[i].distance )
            {
                minValue = g_DistanceTerm[i].distance;
                nextNode = i;
            }
        }
    }
    
    visited[ g_DistanceTerm[ nextNode ].toIndex ] = true;
    return nextNode;

    }

    void PrintAnswerByMST( int numOfArtic )
    {
    bool visited[ MAXSIZE ];

    for( int i = 0 ; i < MAXSIZE ;i++ )
    {
        visited[ i ] = false;
    }
    
    int sPos = 0;
    double answer = -1;
    
    visited[ 0 ] = true;
    
    while( true )
    {
        bool allPathVisited = true;
    
    
        for( int i = 0 ; i < numOfArtic ; i++ )
        {
            if( visited[ i ] == false )
            {
                allPathVisited = false;
                break;
            }
        }
    
        if( allPathVisited )
        {
            break;
        }
    
        int nextNode= FindNextNode( visited, sPos, numOfArtic );
    
    //  cout << nextValue << endl;
    
        if( answer < g_DistanceTerm[ nextNode ].distance )
        {
            answer =  g_DistanceTerm[ nextNode ].distance;
        }
    
        sPos = g_DistanceTerm[ nextNode ].toIndex;
    }
    
    cout.setf(ios::fixed);
    cout.precision(2);
    cout << answer << endl;

    }


    10년 전
1개의 댓글이 있습니다.
  • pikakr
    pikakr

    해결했습니다!


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.