(코테) 프로그래머스_등산코스 정하기 *다익스트라

 

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/118669

 

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        class Edge {
            public int to;
            public int w;
            Edge(int to,int w){
                this.to = to;
                this.w = w;
            };
        }
        class status {
            public int node;
            public int hard;
            status(int node,int hard){
                this.node = node;
                this.hard = hard;
            };
        }
        List<List<Edge>>  list= new ArrayList<>();
        
        int DIF = Integer.MAX_VALUE;
        int[] dist = new int[n+1];
        Arrays.fill(dist,DIF);
        
        boolean[] gateArray = new boolean[n+1];
        boolean[] sumitArray = new boolean[n+1];
        
        for(int next : gates) gateArray[next] =true;        
        for(int next : summits) sumitArray[next] =true;                 
        
        for(int i =0;i<n+1;i++){ list.add(new ArrayList<>()); }
        
        //그래프 완성
        for(int[] next:paths){
            int from =next[0];
            int to =next[1];
            int w =next[2];                        
            list.get(from).add(new Edge(to,w));
            list.get(to).add(new Edge(from,w));            
        }       
        
        PriorityQueue<status> q = new PriorityQueue<>(Comparator.comparingInt(s->s.hard));
        
        for(int next : gates){
            q.offer(new status(next,0));
        }
        
        while(!q.isEmpty()){
            status sta =q.poll();
            int node =sta.node;
            int hard =sta.hard;            
            
            if(hard > dist[node] ) continue;
            if (sumitArray[node]) continue;
            
            for(Edge next:list.get(node)){
                int node2 = next.to;
                int w = next.w;
                
                int max = Math.max(w,hard);
                if(dist[node2]>max){     
                    dist[node2] = max;
                    q.offer(new status(node2,max));
                }                
            }            
        }
        
        Arrays.sort(summits);
        int min = Integer.MAX_VALUE;
        int index = -1;
        for(int next:summits){
            if(dist[next]<min){
                min=dist[next];
                index=next;
            }                        
        }
                                
        return new int[]{index,min};
    }
}

 

 

 

회고.  (다익스트라)

1. 여러 노드(등산 지점들) , 간선 (등산 지점까지 가는 시간)

 

2.출발지 배열, 목적지 배열, 각 등산 지점들 간의 로그?  제공

 

3. 예외조건들 제공 (출발지-> 다른출발지 가면 안됨.)

 

4. 현재 노드에서 연결된 간선들 뻗어 나가는데  항상 최대 가중치를  가지고 뻗어나감.

-> 현재 노드의 가중치와 다음 뻗어 나갈 노드의 시간을 비교해서 더 큰 값을 항상 유지하며 가져감.

dist 배열은 각 노드별 가중치 최소값을 갱신시킴     각 노드별 가중치 최솟값과  위 최대값을 비교해서  만약 갱신된다면 update

 

dist에는 가중치중 최소값을 , 뻗어 나가는 값에는 가중치 최대값을  가중치 값의 비교는 현재 가중치값과 다음 뻗어날 간선의 크기로 비교.

 

 

 

5. 큐 정렬  

-> PriorityQueue<T> list  = new   PriorityQueue<T>(Comparator.comparing(s->s.hard)); 

int로 Status 객체의 hard 멤버변수를 기준으로 int  오름차순 정렬