남극기지 문제 관련해서 질문 있습니다!(코드있습니다) 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 해결했습니다! 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
1개의 댓글이 있습니다. pikakr 해결했습니다! 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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;
}
double g_ArticLength[ MAXSIZE ][ MAXSIZE ];
DistanceTerm g_DistanceTerm[ MAXSIZE * MAXSIZE ];
int g_MSTTableInex = 0;
int main()
{
int numOfCase = 0;
int tryOfCase = 0;
}
void InitVariable()
{
for( int i = 0 ; i < MAXSIZE; i++ )
for( int j = 0 ; j < MAXSIZE; j++ )
{
g_ArticLength[ i ][ j ] = INFINITE;
}
}
void GetDataFromUser( AXIS* artic, int numOfArtic )
{
}
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;
}
int FindNextNode( bool *visited, int sPos, int numOfArtic )
{
int nextNode = 0;
int minValue = INFINITE;
}
void PrintAnswerByMST( int numOfArtic )
{
bool visited[ MAXSIZE ];
}
10년 전
1개의 댓글이 있습니다.
pikakr
해결했습니다!
10년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.