주어진 입력 기지에 대하여 모든 기지가 연결될 경우 그중 최대한 긴 거리를 구하는 문제입니다.
각각의 기지에 대해서 최소거리인 다른 기지를 구하고,
현재까지 연결된 기지에 대해서 연결되지 않은 최단거리의 다른 기지를 구하는 알고리즘을 구현하고자 했는데요 ㅠㅠㅠ
일단 문제에 기술된 예제에 대해서는 정답이 뜨지만
전체를 돌려봣더니 값이 안나오더라구요... ㅠㅠ
#include <iostream>#include <cmath>usingnamespacestd;floata;floatdis[100][100];floatx[100],y[100];intN;intreturn_min(inti){floatmin=dis[i][0];intminj=0;for(intj=1;j<N;j++){if(dis[i][j]<min){min=dis[i][j];minj=j;}}returnminj;}intmain(){intC;a=4000;cin>>C;for(intc=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 일경우 종료floatmax=0;intcount_node=0;int*node;cin>>N;node=newint[N];//각 점 값 입력, 이어진간선의 갯수 입력for(intn=0;n<N;n++){cin>>x[n]>>y[n];node[n]=0;}//각점 사이의 값 입력for(intj=0;j<N;j++){//초기화//max = 0;for(intq=0;q<N;q++){if(q==j)node[q]=1;elsenode[q]=0;}for(inti=0;i<N;i++){for(intj=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++){floatmin=a;intmini=0;for(inti=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);}return0;}}
3번쨰 자리에서 반올림에 문제가 있어 야간 수정했습니다 ㅠㅠ 그리고 return_min의 node가 0인 원소들의 확인의 경우, 이미 연결된 위치(node = 1 인경우)에 대하여 해당 연결값을 최고값 a(1000000)으로 바꿔 줌으로써, 다른 거리 최소값에 대하여 검사가 불가능 하게 해놨습니다. ㅠ
jkd
주어진 입력 기지에 대하여 모든 기지가 연결될 경우 그중 최대한 긴 거리를 구하는 문제입니다.
각각의 기지에 대해서 최소거리인 다른 기지를 구하고,
현재까지 연결된 기지에 대해서 연결되지 않은 최단거리의 다른 기지를 구하는 알고리즘을 구현하고자 했는데요 ㅠㅠㅠ
일단 문제에 기술된 예제에 대해서는 정답이 뜨지만
전체를 돌려봣더니 값이 안나오더라구요... ㅠㅠ
10년 전