importjava.io.FileInputStream;importjava.util.Scanner;publicclassMain{staticinttestCase;staticintN;staticfloatcenterPoint[][];staticfloatdistance[];staticfloatdistanceVia[][];staticfloatvisitPoint[][];staticfloatminDistance[];staticfloatRst=0;staticintCP=0;staticStringoutput;publicstaticfloatgetDistance(floati,floatj,floatk,floatl){floatdistance=0;distance=(i-k)*(i-k)+(j-l)*(j-l);returndistance;}publicstaticvoidmain(String[]args)throwsException{// TODO Auto-generated method stubScannersc=newScanner(System.in);testCase=sc.nextInt();for(inti=1;i<=testCase;i++){N=sc.nextInt();centerPoint=newfloat[N][2];for(intj=0;j<N;j++){centerPoint[j][0]=sc.nextFloat();centerPoint[j][1]=sc.nextFloat();}distance=newfloat[N*N];visitPoint=newfloat[N][N];distanceVia=newfloat[N][N];minDistance=newfloat[N];//알고리즘 구현//기준점에 대한 각 포인트 별 거리 구하기for(intj=0;j<N;j++){for(intk=0;k<N;k++){distanceVia[j][k]=getDistance(centerPoint[j][0],centerPoint[j][1],centerPoint[k][0],centerPoint[k][1]);}}for(intj=0;j<N;j++){dfs(CP,-1);CP++;if(CP==N){CP=0;break;}}for(intj=0;j<N;j++){for(intk=0;k<N;k++){if((visitPoint[j][k]>minDistance[j])&&visitPoint[j][k]!=0&&visitPoint[j][k]!=-1){minDistance[j]=visitPoint[j][k];}}}for(intj=0;j<N;j++){if(Rst==0||Rst>minDistance[j]){Rst=minDistance[j];}}output=String.format("%.2f",Math.sqrt(Rst));Rst=0;System.out.println(output);}}staticvoiddfs(intstart,floatminVal){floatminValue=-1;intp=0;visitPoint[CP][start]=minVal;for(inti=0;i<N;i++){if((minValue==-1||minValue>distanceVia[start][i])&&distanceVia[start][i]!=0){if(visitPoint[CP][i]!=0){continue;}minValue=distanceVia[start][i];p=i;}}for(inti=0;i<N;i++){if(visitPoint[CP][i]==0){dfs(p,minValue);}}}}
제가 구현하려고 했던 알고리즘은 아래와 같습니다.
각 정점별로 짧은 거리에 있는 기지들을 연결한다.(한번 방문했던
기지는, 재방문 하지 않는다. 출발기지는 방문한 기지에 포함한다)
(ex 기지가 총 5개인 경우 - 1->5->3->4->2 )
위 절차를, 1번째 기지부터, N번째 기지까지 반복한다.
위 절차가 완료되면, 각 기지별로, 가장 긴 거리들을 구한다.
가장 긴 거리들 중, 가장 짧은 거리를 구하여 답을 도출한다.
제가 생각했던 알고리즘을, DFS알고리즘을 이용하여, 풀려고 했으나, 실패했습니다... 부끄러운 얘기지만, 혼자힘으로 풀려고, 해당 문제를 거의 3주째 보고 있는데, 쉽지가 않습니다.
고수님들의 조언 부탁드립니다.
huming10
오답소스 입니다.
제가 구현하려고 했던 알고리즘은 아래와 같습니다.
각 정점별로 짧은 거리에 있는 기지들을 연결한다.(한번 방문했던
기지는, 재방문 하지 않는다. 출발기지는 방문한 기지에 포함한다)
(ex 기지가 총 5개인 경우 - 1->5->3->4->2 )
위 절차를, 1번째 기지부터, N번째 기지까지 반복한다.
위 절차가 완료되면, 각 기지별로, 가장 긴 거리들을 구한다.
가장 긴 거리들 중, 가장 짧은 거리를 구하여 답을 도출한다.
제가 생각했던 알고리즘을, DFS알고리즘을 이용하여, 풀려고 했으나, 실패했습니다... 부끄러운 얘기지만, 혼자힘으로 풀려고, 해당 문제를 거의 3주째 보고 있는데, 쉽지가 않습니다.
고수님들의 조언 부탁드립니다.
8년 전