남극기지 문제

  • huming10
    huming10

    오답소스 입니다.

    import java.io.FileInputStream;
    import java.util.Scanner;
    
    public class Main {
    
        static int testCase;
        static int N;
        static float centerPoint[][];
        static float distance[];
        static float distanceVia[][];
        static float visitPoint[][];
        static float minDistance[];
        static float Rst = 0;
        static int CP=0;
        static String output;
    
    
        public static float getDistance(float i, float j, float k, float l){
            float distance = 0;
            distance = (i - k)*(i - k) + (j-l)*(j-l); 
            return distance;
        }
        public static void main(String[] args) throws Exception{
            // TODO Auto-generated method stub
    
            Scanner sc = new Scanner(System.in);
    
            testCase = sc.nextInt();
            for( int i = 1 ; i <= testCase ; i++){
                N = sc.nextInt();
                centerPoint = new float[N][2];
                for(int j = 0 ; j < N ; j++)
                {
                    centerPoint[j][0] = sc.nextFloat();
                    centerPoint[j][1] = sc.nextFloat();
                }
                distance = new float[N*N];
                visitPoint = new float[N][N];
                distanceVia = new float[N][N];
                minDistance = new float[N];
    
                //알고리즘 구현
                //기준점에 대한 각 포인트 별 거리 구하기
                for(int j = 0 ; j < N ; j++){
                    for(int k = 0 ; k < N ; k++){                   
                            distanceVia[j][k] = getDistance(centerPoint[j][0], centerPoint[j][1], 
                                centerPoint[k][0], centerPoint[k][1]);
                        }
                    }
    
    
                for(int j = 0; j < N ; j++)
                {
                    dfs(CP, -1);
                    CP++;
                    if(CP == N)
                    {
                        CP = 0;
                        break;
                    }
                }
    
    
                for(int j = 0 ; j < N ; j++){
                    for(int k = 0 ; k < N ; k++){
                        if((visitPoint[j][k] > minDistance[j] ) && visitPoint[j][k]!= 0 && visitPoint[j][k]!= -1){
                            minDistance[j] = visitPoint[j][k];  
                        }
                    }               
                }
    
                for(int j = 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);
            }       
        }
    
        static void dfs(int start, float minVal){
    
    
            float minValue = -1;
            int p = 0;
    
            visitPoint[CP][start] = minVal;
    
            for(int i = 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(int i = 0 ; i < N ; i++){
                if( visitPoint[CP][i] == 0 ){
                    dfs(p, minValue);
                }
            }
        }
    }
    

    제가 구현하려고 했던 알고리즘은 아래와 같습니다.

    각 정점별로 짧은 거리에 있는 기지들을 연결한다.(한번 방문했던
    기지는, 재방문 하지 않는다. 출발기지는 방문한 기지에 포함한다)
    (ex 기지가 총 5개인 경우 - 1->5->3->4->2 )
    위 절차를, 1번째 기지부터, N번째 기지까지 반복한다.

    위 절차가 완료되면, 각 기지별로, 가장 긴 거리들을 구한다.

    가장 긴 거리들 중, 가장 짧은 거리를 구하여 답을 도출한다.

    제가 생각했던 알고리즘을, DFS알고리즘을 이용하여, 풀려고 했으나, 실패했습니다... 부끄러운 얘기지만, 혼자힘으로 풀려고, 해당 문제를 거의 3주째 보고 있는데, 쉽지가 않습니다.
    고수님들의 조언 부탁드립니다.


    7년 전
2개의 댓글이 있습니다.
  • dya2122
    dya2122

    반올림은 구현 하셨어요??


    7년 전 link
  • JongMan
    JongMan

    말씀하신 알고리즘이 잘 이해가 안 가네요. 각 정점에서 가장 가까운 정점을 연결해서 서브그래프를 만들고, 여기에서 가장 긴 간선을 구한다는 말씀이신가요? 그럼 DFS는 한 번만 하는 것 같은데 왜 여러 번 하나요?


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