[프로그래머스] 등산코스 정하기

       문제 요약        

- 문제

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

프로그래머스

 

         아이디어        

2가지 문제 해결에 중요한 요소가 있다.

 

첫번째는 단방향, 양방향을 구분해야 했다.

입구일 경우 다른 곳으로만 갈 수 있는 단방향이다. 

산봉우리일 경우 산으로 오는 단방향이다. (이는 출발지 > 산봉우리의 Intensity를 구하면 산봉우리 > 도착지 는 같기 때문이다)

 

두번째는 지금까지의 Intensity vs 다음까지 경로를 진행했을 때의 Intensity 를 비교하여 

다음 경로를 진행할지 말지를 결정한다.  

         소스코드        

import java.util.*;
class Solution {
    static List<Node>[] adj;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
    	// 인접비열 만들기 
        adj = new ArrayList[n+1];
        for(int i = 0; i < n+1; i++) {
            adj[i] = new ArrayList<>();
        }
        
        Set<Integer> sans = new HashSet<>();
        for(int i = 0; i < summits.length; i++) {
            sans.add(summits[i]);
        }
        
        Set<Integer> gate = new HashSet<>();
        for(int i = 0; i < gates.length; i++) {
            gate.add(gates[i]);
        }
        
        
        for(int i = 0; i < paths.length; i++) {
            int x = paths[i][0];
            int y = paths[i][1];
            int w = paths[i][2];
            if(gate.contains(x) || sans.contains(y)) { // 단방향 통신로 
                adj[x].add(new Node(y,w));
            }else if(gate.contains(y) || sans.contains(x)) { // 단방향 통신로 
                adj[y].add(new Node(x,w));
            }else {
                adj[x].add(new Node(y, w));
                adj[y].add(new Node(x, w));        
            }
        }
        
        
       return dikstra(n, gates, summits); // 
        
    }
    static int[] dikstra(int n, int[] gates, int[] summits) {
        int[] sanIntensity = new int[n+1];
        Arrays.fill(sanIntensity, Integer.MAX_VALUE);
        
        Queue<Node> queue = new ArrayDeque<>();
        for(int i = 0; i < gates.length; i++) {
            queue.add(new Node(gates[i], 0)); // 모든 시작 지점에서부터 시작
            sanIntensity[gates[i]] = 0;
        }
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            if(sanIntensity[now.x] < now.cost) { // 현재 cost 보다 작다면
                continue;
            }
        
            for(Node next : adj[now.x]) {
                int intensity = Math.max(next.cost, sanIntensity[now.x]);
                if(sanIntensity[next.x] > intensity) {
                    sanIntensity[next.x] = intensity;
                    queue.add(new Node(next.x, intensity));
                }
            }
        }
        
        int sanId = 0, minIntensity = Integer.MAX_VALUE;
    
        Arrays.sort(summits);
        
        for(int s : summits) {
            if(sanIntensity[s] < minIntensity) {
                minIntensity = sanIntensity[s];
                sanId = s;
            }
        }
        return new int[]{sanId, minIntensity};
        
    }
    static class Node implements Comparable<Node>{
        int x, cost;
        Node(int x, int cost) {
            this.x = x;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}

어려워요... 할 수 있을 거 같은데 할 수 없는 이 느낌...