ARCTIC 남극 기지 문제입니다.

  • jkd
    jkd

    주어진 입력 기지에 대하여 모든 기지가 연결될 경우 그중 최대한 긴 거리를 구하는 문제입니다.

    각각의 기지에 대해서 최소거리인 다른 기지를 구하고,
    현재까지 연결된 기지에 대해서 연결되지 않은 최단거리의 다른 기지를 구하는 알고리즘을 구현하고자 했는데요 ㅠㅠㅠ

    일단 문제에 기술된 예제에 대해서는 정답이 뜨지만
    전체를 돌려봣더니 값이 안나오더라구요... ㅠㅠ

    #include <iostream>
    #include <cmath>
    using namespace std;
    
    float a;
    float dis[100][100];
    float x[100], y[100];
    int N;
    
    int return_min(int i)
    {
        float min = dis[i][0];
        int minj = 0;
        for(int j = 1; j < N ; j++)
        {
            if(dis[i][j] < min)
            {
                min = dis[i][j];
                minj = j;
            }
        }
    
        return minj;
    }
    
    
    int main()
    {
        int C;
        a = 4000;
        cin >> C;
    
        for(int c = 0; c < C ; c++)
        {
            //0 에서 가장 짧은 거리 t1를 구함 - 0,t1, t1,0 은 a(최댓값)으로 변경
            // 0, t1 에서 가장 짧은거리 t2 를 구함 - 0,t2) t2,0 /  t1,t2  / t2,t1  = a 로 변경
            // 0, t1, t2, 에서 가장 짧은거리 t3 를 구함
            //.. 각각의 값에 대하여 이전에 구해진 값은 제외하며, 모든 점이 연결되었을 경우 count_node = N-1 일경우 종료
            float max = 0;
            int count_node = 0;
            int *node;
    
            cin >> N;
    
            node = new int[N];
    
            //각 점 값 입력, 이어진간선의 갯수 입력
            for(int n = 0 ; n < N ; n++)
            {
                cin >> x[n] >> y[n];
                node[n] = 0;
            }
    
    
            //각점 사이의 값 입력
            for(int j = 0 ; j < N ; j++)
            {
                //초기화
                //max = 0;
                for(int q = 0; q < N ; q++)
                {
                    if (q == j )
                        node[q] = 1;
                    else
                        node[q] = 0;
                }
    
    
                for(int i = 0; i < N; i++)
                {
                    for(int j = i+1; j < N ; j ++)
                    {
                        dis[i][j] = dis[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
                    }
                    dis[i][i] = a;
                }
                ////////////////////
    
                for(count_node = 0 ; count_node < N-1 ; count_node++)
                {
                    float min = a;
                    int mini = 0;   
    
                    for(int i = 0; i < N ; i++)
                    {
                        if(node[i] == 1 && dis[i][return_min(i)] < min)
                        {
                            min = dis[i][return_min(i)];
                            mini = i;
                        }
                    }
    
                    node[return_min(mini)] = 1;
    
                    if(max < dis[mini][return_min(min)])
                        max = dis[mini][return_min(mini)];
                    dis[mini][return_min(mini)] = dis[return_min(mini)][mini]  = a;
    
                    //printf(" %.2f\n",max);
                }
            }
    
            printf("%.2f\n",max);
        }
        return 0;
    }
    }
    

    10년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    제대로 보진 못했는데, return_minnode가 0인 원소들만 확인해야 하는 것 아닌가 싶습니다.


    10년 전 link
  • jkd
    jkd

    3번쨰 자리에서 반올림에 문제가 있어 야간 수정했습니다 ㅠㅠ 그리고 return_min의 node가 0인 원소들의 확인의 경우, 이미 연결된 위치(node = 1 인경우)에 대하여 해당 연결값을 최고값 a(1000000)으로 바꿔 줌으로써, 다른 거리 최소값에 대하여 검사가 불가능 하게 해놨습니다. ㅠ


    10년 전 link
  • JongMan
    JongMan

    minireturn_min 사이의 연결값만 바뀌니까 같은 정점이 두 번 선택될 수 있는 것 아닌가요?
    그리고 반올림은 저렇게 안하셔도 됩니다. .2f가 반올림을 해 줍니다.


    10년 전 link
  • jkd
    jkd

    음 2.f가 반올림이 되는군요 ㅎㅎ 처음알앗네요 ;;

    음... 이제는 런타임 오류가... 어디서 오버프롤우가 뜨는지 감이 안잡히네요... ㅠㅠ


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