#include <stdio.h>#include <stdlib.h>#include <math.h>#define TRUE 1#define FALSE 0#define MAX_POINT_NUM 103 /* 100 + 2 + 1 */shortintvisited[MAX_POINT_NUM];typedefstructPoint*PointPointer;structPoint{intname;intx;inty;};typedefstructadj_list*adj_listPointer;structadj_list{intdata;adj_listPointerlink;};adj_listPointer*adj_header_list=(adj_listPointer*)malloc(MAX_POINT_NUM*sizeof(adj_listPointer));PointPointer*Stone_list=(PointPointer*)malloc(MAX_POINT_NUM*sizeof(PointPointer));doublejump;intN;intnum=0,cnt=0;doubledist(inti,intn){intdistx=(Stone_list[i])->x-(Stone_list[n])->x;intdisty=(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); */doubledist=(double)(distx*distx+disty*disty);dist=sqrt(dist);returndist;}voidAdd_adj(inthead,inttail){adj_listPointerx;adj_listPointertemp=(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;}voidFind(){inti=0;while(i<num){doubled=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++;}}voiddfs(intv){/* depth first search of a graph beginning at v */adj_listPointerw;visited[v]=TRUE;cnt++;for(w=adj_header_list[v];w;w=w->link){if(!visited[w->data])dfs(w->data);}}voidInit(){cnt=0;num=0;for(inti=0;i<MAX_POINT_NUM;i++){Stone_list[i]=0;adj_header_list[i]=0;}}voidAdd_to_Stone_list(){intposx,posy;scanf("%d",&posx);scanf("%d",&posy);PointPointertemp=(Point*)malloc(sizeof(Point));temp->x=posx;temp->y=posy;temp->name=num;Stone_list[num]=temp;}voidTask(){Add_to_Stone_list();Find();num++;}voidFREE(){for(inti=0;i<MAX_POINT_NUM;i++){if(Stone_list[i]){free(Stone_list[i]);}if(adj_header_list[i]){adj_listPointerp,temp;p=adj_header_list[i];while(p){temp=p->link;free(p);p=temp;}}}}intmain(){intcases;scanf("%d",&cases);while(cases--){Init();intjump_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++로 코딩할떄도 메모리수동관리를 하지 않는게 좋은가요?)
전체 그래프가 연결되어야만 탈출할 수 있는 것은 아니죠. 일부가 끊어져 있더라도 출발 지점과 도착 지점만 연결되면 탈출이 가능합니다.
그리고 메모리 관리 이야기는 하도 코드를 제대로 못짜니 그렇게 쓰여있는 것 같은데, 제대로만 한다면 큰 문제는 없습니다. 가장 문제되는 것은 신경 쓸 것이 더 많아져서, 결국 코딩 실수가 더 잦아지는 것이겠죠. 그 외에 드물긴 하지만 매우 잦은 메모리 할당/해제가 성능에 영향을 주는 경우는 있습니다.
oanoelsis
BRAVEDUCK문제 알고리즘에 대한 질문인데요. 제가 짠 알고리즘은 먼저 출발점과 도착점을 포함, 모든 돌들의 좌표를 번호를 매겨 1차원 어레이에 차곡차곡 쌓으면서 각 입력을 받을때마다 기존에 받았던 좌표들과 비교하여 거리가 주어진 점프가능거리보다 작은 거리에 있는 좌표들을 adjacency list에 추가하도록 만들었습니다. 그래서 입력을 다 받고 나면 거리가 점프거리보다 가까운 점들끼리는 edge가 존재하도록 graph가 만들어지게 됩니다. 그 다음에 만약 이 그래프가 모두 connected되어있다면 오리가 점프해서 출발점에서 마지막까지 갈수 있다는 이야기가 되니까, DFS(0) spannig tree를 만드는 알고리즘을 돌려서 dfs가 한번 작동할떄마다 카운트수를 한개 씩 늘렷습니다. 마지막으로 DFS(0) spanning tree의 점 개수와 주어진 전체 점 개수가 일치한다면 모두다 연결되있는 그래프인 것이고 일치하지 않는다면 중간에 끊어져있는 그래프인 것이라는 사실을 이용해 YES, NO를 판별하였습니다.
이 알고리즘이 틀리다는 반례가 될만한 예제나 틀린 이유를 알고 싶습니다.
(그리고 , 추가로 메모리관리를 수동으로 하는 코딩은 되도록 지양하는 것이 좋다고 자주하는실수 모음에 써져있는데요. 그럼 c++로 코딩할떄도 메모리수동관리를 하지 않는게 좋은가요?)
10년 전