ACRTIC 문제 질문 드립니다.

  • kwonmha
    kwonmha

    ARCTIC을 풀고 있습니다.
    Test Case에서는 답이 잘 나오는데
    제출하니 오답이 뜨네요.

    알고리즘은 이분법을 사용했습니다.
    이분법으로 거리를 조절해 가면서
    모든 기지들이 0과 연결되는지 재귀 함수를 통해 확인합니다.
    0번 기지와 연결된 게 잘못됐을 수 있을 거 같은데 잘 모르겠습니다.

    도움 부탁드립니다. ㅜ

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    
    #pragma warning(disable:4996)
    
    using namespace std;
    
    int baseNum, memo[100];
    double pos[100][2], dist[100][100], farthest;
    bool connected[100][100], visited[100][100];
    
    double max(double a, double b){
        return a >= b ? a : b;
    }
    
    void GetFarthestDistance(){
        for (int i = 0; i < baseNum; i++){
            for (int j = i + 1; j < baseNum; j++){
                dist[i][j] = sqrt(pow(pos[i][0] - pos[j][0], 2) + 
                                    pow(pos[i][1] - pos[j][1], 2));
                farthest = max(farthest, dist[i][j]);           
            }
        }
    }
    
    // 0과 연결되어 있는지
    bool IsConnected(int base){
        if (connected[0][base]) return true;
        int& ret = memo[base];
        if (ret != -1) { 
            //printf("%d\n", ret); 
            return ret; 
        }
        for (int i = 1; i < baseNum; i++){
            if (i == base) continue;
            // 이미 지나온 도시는 안 가보도록
            if ((i >= base && visited[base][i])
                || (i < base && visited[i][base])) continue;
            if ((i >= base && connected[base][i])
                || (i < base && connected[i][base])){
                visited[i][base] = visited[base][i] = true;
                ret = IsConnected(i);
                if (ret) return ret;
            }       
        }
        return 0;
    }
    
    bool IsAllConnected(){
        memset(memo, -1, sizeof(memo));
        for (int base = 1; base < baseNum; base++){
            memset(visited, 0, sizeof(visited));
            if(!IsConnected(base))
                return false;
        }
        return true;
    }
    
    // gap 이하의 길이로 선을 연결해서 모든 점이 연결되는지 확인
    bool Decision(double gap){
        memset(connected, 0, sizeof(connected));
        for (int i = 0; i < baseNum; i++){
            for (int j = i + 1; j < baseNum; j++){
                if (dist[i][j] <= gap)
                    connected[i][j] = true;
                //printf("%.2lf ", dist[i][j]);
            }
            //printf("\n");
        }
        return IsAllConnected();
    }
    
    double Optimize(){
        double lo = 0, hi = farthest;
        for (int it = 0; it < 100; it++){
            double mid = (lo + hi) / 2.0;
            //printf("%.2lf\n", mid);
            if (Decision(mid))
                hi = mid; // 기존 거리로 도달되면 거리를 줄인다
            else
                lo = mid; // 기존 거리로 안되면 거리를 늘린다
        }
        return lo;
    }
    
    int main(void){
        /*bool a = 5;
        bool b = 0;
        bool c = -1;
        printf("%d %d %d\n", a, b, c); => 1 0 1*/
        freopen("input.txt", "r", stdin);
        int tc;
        scanf("%d", &tc);
    
        for (int i = 0; i < tc; i++){
            farthest = 0;   
            scanf("%d", &baseNum);
            for (int j = 0; j < baseNum; j++){
                scanf("%lf %lf", &pos[j][0], &pos[j][1]);
            }
            GetFarthestDistance();
            printf("%.2lf\n", Optimize());
        }
    
        return 0;
    }
    

    8년 전
4개의 댓글이 있습니다.
  • seico75
    seico75

    호..혹시 반올림??


    8년 전 link
  • kwonmha
    kwonmha

    음... 반올림 문제는 %.2lf 이걸로 해결되지 않나요?ㅎㅎ


    8년 전 link
  • seico75
    seico75

    printf 의 rounding 이 우리가 아는 반올림과는 조금 다르게 동작합니다.
    아래코드로 한번 테스트 해보시죠.

    #include <stdio.h>
    
    int main( void)
    {
        float f;
    
        f = 1.21; 
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.22;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.23;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.24;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.25;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.26;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.27;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.28;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
        f = 1.29;
        printf( "%.2lf %.2lf %.2lf\n", f+0.004, f+0.005, f+0.006);
    
        return 0;
    }
    

    저는 아래와 같이 나오네요.

    1.21 1.22 1.22
    1.22 1.23 1.23
    1.23 1.24 1.24
    1.24 1.25 1.25
    1.25 1.25 1.26
    1.26 1.26 1.27
    1.27 1.27 1.28
    1.28 1.28 1.29
    1.29 1.29 1.30


    8년 전 link
  • kwonmha
    kwonmha

    답변 감사합니다. 반올림에 문제라기보단 알고리즘에 허점이 있었네요.
    Random number 생성을 통해서 test case를 10개 생성한 후에
    다른 공개된 정답 소스와 비교해 답이 다른 68개짜리 case가 하나 있어서
    노가다를 통해 6개로 줄이고 원인을 알아냈습니다. ㅋㅋㅋ

    원인은
    ~~
    int& ret = memo[base];
    if (ret != -1) {
    //printf("%d\n", ret);
    return ret;
    }
    ~~

    이 부분이었는데요,
    한 번 연결이 안 된다고 판별한 기지가 나중엔 다시 연결되는 경우가 생기더라고요.
    예를 들어 기지들이 1차원에
    3 2 1 4 0 이런 식으로 되어 있는데
    1번이 연결되어 있는지 확인할 때, 재귀적으로 2,3을 탐색한 후 못간다고 생각해 놓으면
    1번에 대한 판별을 마친 후 2를 판별할 때 못간다고 결정해버려서

    ~~
    int& ret = memo[base];
    if(ret == 1) return ret;
    ~~
    이런 식으로 바꿨더니 해결됐습니다.


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