[프로그래머스 ,Java] Level3: 등산코스 정하기

 

문제분석

 

문제목표 :  출발점과 산봉우리의 intensity가 최소가되는 등산코스를 정해주세요.

 

특징1.  Intensity는  각노드마다 휴식없이 이동하는 거리다.  노드마다는 휴식공간이 있다.

특징2. 산봉우리는 코스에 단 1개만 존재해야한다.

 

 

 

 

처음 접근:  플로이드 와샬 사용

 

->  여러개의 출발점과  여러개의 산봉우리가  존재하기때문에,

 

모든 정점과 모든 정점의 최소거리를 구하는 알고리즘을 사용했다.

 

단, 이 문제는 최소거리가 아닌  Intensity를 구해야하므로  알고리즘을 고쳐 사용해야한다.

 

 

-> 결과:  정확성 O   효율성 에러

 

생각되는 이유:   원하는 출발점 -> 산봉우리의 Intensity는 구할수있지만,

 

그외의 경우,

경유지->경유지,  산봉우리->산봉우리, 출발점 -> 출발점 과같은 케이스들의 쓸데없는연산은 할필요가없다.

 

아무래도 3중반복문을 돌리다보니 문제가 되는것같다..

 

 

두번째 접근 : 다익스트라 알고리즘 (BFS+DP)

 

->  다익스트라는  한개의 출발점과   다른 여러노드의 최소거리를 구하는 알고리즘이다.

 

이 다익스트라를  조금 활용하면   특정한 여러개의 출발점과  다른 노드의 최소거리를 구할수있다.

 

 

다익스트라 알고리즘은 

 

특정출발지 ->  다른노드의 최소거리를  1차원 배열로 저장한다. 

 

그후, 출발지의 (자기자신) 노드는 0으로 잡고, 나머지는 매우큰 숫자를 넣는다.

 

출발지를 여러개로 잡는법은 꽤 간단하다.  그냥 새로운 출발지를 하고싶은 노드에 0값을 부여하면 끝이다.

 

그 후,  BFS안에다 출발노드를 입력하면된다.

 

 

문제풀이

import java.util.*;
class Node {
    
    public int index;
    public int dist;
    
    public Node(int index, int dist){
        this.index=index;
        this.dist=dist;
    }
    
}
 
class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = {};
        
        int[] dist = new int [n+1];
        // int[][] map = new int [n+1][n+1];
        List<Node>[] map = new ArrayList[n+1];
        
        for (int i = 0; i <= n; i++) map[i] = new ArrayList<>();
        
        Arrays.fill(dist, 10000001);
       
        int[] check = new int[n+1];
        
        for(int i=0;i<gates.length;i++){
            check[gates[i]]=-1;
        }
        
        for(int i=0;i<summits.length;i++){
            check[summits[i]]=-2;
        }
                  
        
        for(int i =0;i<paths.length;i++){
 
            int s = paths[i][0];
            int e = paths[i][1];
            int d = paths[i][2];
 
            if(check[s]==-1||check[e]==-2){
                map[s].add(new Node(e,d));
            }
            else if(check[e]==-1||check[s]==-2){
                map[e].add(new Node(s,d));
            }
            else{
                map[e].add(new Node(s,d));
                map[s].add(new Node(e,d));
            }
        }
        
        Queue<Node> pq = new PriorityQueue<>(Comparator.comparing(o->o.dist));
        
        //초기값
        for(int g: gates){
            dist[g]=0;
           
            pq.add(new Node(g,dist[g]));
        }
        
          while(!pq.isEmpty()){
        
            Node current = pq.poll();
     
            int idx =current.index;
            
            if(current.dist > dist[current.index]){
                continue;
            }
            
            // for(int s : summits){
            //     if(idx==s){
            //         continue Loop;
            //     }
            // }    
     
            for(Node node : map[idx]){            
                    if(dist[node.index] > Math.max(dist[idx],node.dist)){
                        dist[node.index] = Math.max(dist[idx],node.dist);
                        pq.add(node);
                    }  
            }     
        }
        
        Arrays.sort(summits);
 
        int[] result = new int[]{0, Integer.MAX_VALUE};
 
        
        for (int summit : summits) {
            if (dist[summit] < result[1]) {
                result[1] = Math.min(result[1], dist[summit]);
                result[0] = summit;
            }
        }
  
        return result;
    }
}