BRAVEDUCK문제 알고리즘 질문입니다.

  • oanoelsis
    oanoelsis

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define TRUE 1
    #define FALSE 0
    #define MAX_POINT_NUM 103 /* 100 + 2 + 1 */
    short int visited[MAX_POINT_NUM];
    typedef struct Point* PointPointer;
    struct Point{
            int name;
            int x;
            int y;
    };
    
    typedef struct adj_list* adj_listPointer;
    struct adj_list{
            int data;
            adj_listPointer link;
    };
    
    adj_listPointer* adj_header_list = (adj_listPointer*)malloc(MAX_POINT_NUM * sizeof(adj_listPointer));
    
    PointPointer* Stone_list = (PointPointer*)malloc(MAX_POINT_NUM * sizeof(PointPointer));
    
    double jump;
    int N;
    int num=0, cnt=0;
    
    double dist(int i, int n){
            int distx = (Stone_list[i])->x - (Stone_list[n])->x;
            int disty = (Stone_list[i])->y - (Stone_list[n])->y;
            /*
            printf("i.x:%d, i.y:%d, num.x:%d, num.y:%d, distx:%d, disty:%d\n",(Stone_list[i])->x, (Stone_list[i])->y, (Stone_list[n])->x, (Stone_list[n])->y, distx, disty);
            */
            double dist = (double)(distx * distx + disty * disty);
            dist = sqrt(dist);
            return dist;
    }
    
    void Add_adj(int head, int tail){
            adj_listPointer x;
            adj_listPointer temp = (adj_listPointer)malloc(sizeof(adj_list));
            temp->data = tail;
            temp->link = 0;
            if(!(adj_header_list[head])){
                    adj_header_list[head] = temp;
                    return;
            }
            x = adj_header_list[head];
            while(x->link!=0){
                    x = x->link;
            }
            x->link=temp; return;
    }
    void Find(){
            int i=0;
            while(i<num){
                    double d = dist(i, num);
                    //printf("i=%d num=%d d=%lf\n", i, num, d);
                    if(jump >= d){/* add to adjacency list */
                            Add_adj(i, num);
                            Add_adj(num, i);
                    }
                    i++;
            }
    }
    
    void dfs(int v){/* depth first search of a graph beginning at v */
            adj_listPointer w;
            visited[v] = TRUE;
            cnt++;
            for(w = adj_header_list[v]; w; w = w->link){
                    if(!visited[w->data])
                            dfs(w->data);
            }
    }
    
    void Init(){
            cnt=0;
            num=0;
            for(int i=0; i<MAX_POINT_NUM; i++){
                    Stone_list[i] = 0;
                    adj_header_list[i] = 0;
            }
    }
    void Add_to_Stone_list(){
            int posx, posy;
            scanf("%d", &posx);
            scanf("%d", &posy);
            PointPointer temp = (Point*)malloc(sizeof(Point));
            temp->x = posx;
            temp->y = posy;
            temp->name=num;
            Stone_list[num] = temp;
    }
    
    void Task(){
            Add_to_Stone_list();
            Find();
            num++;
    }
    void FREE(){
            for(int i=0; i<MAX_POINT_NUM; i++){
                    if(Stone_list[i]){
                            free(Stone_list[i]);
                    }
                    if(adj_header_list[i]){
                            adj_listPointer p, temp;
                            p = adj_header_list[i];
                            while(p){
                                    temp = p->link;
                                    free(p);
                                    p = temp;
                            }
                    }
            }
    }
    int main(){
            int cases;
            scanf("%d", &cases);
            while(cases--){
                    Init();
                    int jump_int=0;
                    scanf("%d", &jump_int);
                    jump = (double)jump_int;
                    /* starting Point */
                    Task();
                    /* end Point */
                    Task();
                    /*number of stone */
                    scanf("%d", &N);
                    while(N--){
                            Task();
                    }
                    dfs(0); /* make DFS(0) spanning Tree */
                    //printf("cnt: %d\n", cnt);
                    //printf("num: %d\n", num);
                    if(cnt == num){
                            printf("YES\n");
                    }
                    else{
                            printf("NO\n");
                    }
                    FREE();
            }
            free(Stone_list);
            free(adj_header_list);
    }
    

    BRAVEDUCK문제 알고리즘에 대한 질문인데요. 제가 짠 알고리즘은 먼저 출발점과 도착점을 포함, 모든 돌들의 좌표를 번호를 매겨 1차원 어레이에 차곡차곡 쌓으면서 각 입력을 받을때마다 기존에 받았던 좌표들과 비교하여 거리가 주어진 점프가능거리보다 작은 거리에 있는 좌표들을 adjacency list에 추가하도록 만들었습니다. 그래서 입력을 다 받고 나면 거리가 점프거리보다 가까운 점들끼리는 edge가 존재하도록 graph가 만들어지게 됩니다. 그 다음에 만약 이 그래프가 모두 connected되어있다면 오리가 점프해서 출발점에서 마지막까지 갈수 있다는 이야기가 되니까, DFS(0) spannig tree를 만드는 알고리즘을 돌려서 dfs가 한번 작동할떄마다 카운트수를 한개 씩 늘렷습니다. 마지막으로 DFS(0) spanning tree의 점 개수와 주어진 전체 점 개수가 일치한다면 모두다 연결되있는 그래프인 것이고 일치하지 않는다면 중간에 끊어져있는 그래프인 것이라는 사실을 이용해 YES, NO를 판별하였습니다.

    이 알고리즘이 틀리다는 반례가 될만한 예제나 틀린 이유를 알고 싶습니다.

    (그리고 , 추가로 메모리관리를 수동으로 하는 코딩은 되도록 지양하는 것이 좋다고 자주하는실수 모음에 써져있는데요. 그럼 c++로 코딩할떄도 메모리수동관리를 하지 않는게 좋은가요?)


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

    전체 그래프가 연결되어야만 탈출할 수 있는 것은 아니죠. 일부가 끊어져 있더라도 출발 지점과 도착 지점만 연결되면 탈출이 가능합니다.

    그리고 메모리 관리 이야기는 하도 코드를 제대로 못짜니 그렇게 쓰여있는 것 같은데, 제대로만 한다면 큰 문제는 없습니다. 가장 문제되는 것은 신경 쓸 것이 더 많아져서, 결국 코딩 실수가 더 잦아지는 것이겠죠. 그 외에 드물긴 하지만 매우 잦은 메모리 할당/해제가 성능에 영향을 주는 경우는 있습니다.


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