[카카오 기출 문제]등산코스 정하기- 레벨 3, 다익스트라 + 시간초과고려

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

프로그래머스

 

다익스트라를 활용하여 푸는 문제입니다.

 

기억해야할점들입니다.

 

첫번째, 다익스트라에 대한 이해가 필요합니다.

다익스트라는 원래 한 점에서 다른 모든 점들까지 가는데 필요한 최소거리를 d[] 라는 배열에 표시해주는 알고리즘입니다.

이번 문제같은경우는 한 노드에서 다른 노드까지 갈때의 가중치의 최솟값을 먼저 구하고 그 이후에 다음 노드와 연결된 가중치의 최대값을 구해주는 문제입니다.

이것을 이해하는것이 가장 중요한 부분입니다.

 

두번째, 산봉우리 이후부터의 연산은 중지시킵니다.

그래야만 다른 산봉우리를 2번 이상 포함하는 경로를 거치지 않습니다.

어처피 다익스트라 알고리즘은 특정 경로를 찾는것이 아닌 한 점에서 모든 경로까지의 최솟값을 구하는 알고리즘입니다. 그러므로 (출입구) - (정상) -(출입구) 라는 방향에서 (출입구) - (정상) 까지만 경로를 구해도 충분합니다.

다익스트라 알고리즘 도중 (정상)을 만난다면 거기서 멈추면됩니다.

if(summitshashset.contains(nowindex))
   continue;

 

세번째, 우리가 구하는 것은 산봉우리 기준에서의 intensity의 최솟값입니다.

for(int i=0;i<summits.length;i++){
    if(d[summits[i]] < answer[1]){
        answer[1] = d[summits[i]];
        answer[0] = summits[i];
    }else if(d[summits[i]] == answer[1] && summits[i] < answer[0]){
        answer[0] = summits[i];
    }
}

 

네번째, 각 출발점에서의 다익스트라 알고리즘을 실행하여 각 intensity를 구한뒤 그것을 비교하여 등산코스를 정한다면 시간초과가 날 수 밖에 없습니다.

문제의 조건에 노드의 개수 = 50,000개, V

등산로의 길이 = 200,000개 , E

우선순위큐를 활용한 다익스트라 시간복잡도 = O( E Log V) 

게이트 1 ≤ gates의 길이 ≤ n

각 게이트마다 모든 반복문을 돌릴시 N * O (E Log V)

여기서는 50,000 * O ( 200,000 * Log 50,000 ) 입니다. 컴퓨터 연산횟수가 1초에 1억번 연산한다고 가정할시 누가봐도 시간초과가 나옵니다.

 

다섯번쨰, 단순 배열에서의 조회확인은 HAshSet.Contains() 로 진행하면 훨씬 빠릅니다.

주석표시한 코드로 실행했을때보다 마지막케이스에서 900MB -> 150MB로 떨어졌습니다.

단순 HAshSet으로 시간이 엄청나게 줄어듭니다.

if(summitshashset.contains(nowindex))
   continue;
// boolean flag = false;
// for(int i=0;i<summits.length;i++){
//     if(summits[i] == nowindex){
//         flag = true;
//     }
// }
// if(flag == true) continue;

 

 

정답코드

import java.util.Map.*;
import java.io.*;
import java.util.*;
class Solution {
    
    public ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    public int d[];
    public Set<Integer> gateshashset = new HashSet<Integer>();
    public Set<Integer> summitshashset = new HashSet<Integer>();   
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        
        for(int a : summits){
            summitshashset.add(a);
        }
        
        //그래프 초기화, 관리를 위해 인덱스 1부터 n까지
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }
        
        d = new int[n+1];
        Arrays.fill(d, Integer.MAX_VALUE);
        
        for(int i=0;i<paths.length;i++){
            int s = paths[i][0];
            int e = paths[i][1];
            int d = paths[i][2];
            
            //양방향 그래프
            graph.get(s).add(new Node(e, d));
            graph.get(e).add(new Node(s, d));
        }
        
        dijkstra(gates, summits);
        
        // for(int a : d)
        //     System.out.println(a);
        
        int[] answer = {0, Integer.MAX_VALUE};
        
        for(int i=0;i<summits.length;i++){
            if(d[summits[i]] < answer[1]){
                answer[1] = d[summits[i]];
                answer[0] = summits[i];
            }else if(d[summits[i]] == answer[1] && summits[i] < answer[0]){
                answer[0] = summits[i];
            }
        }
        
        
        
        return answer;
    }
    
    public void dijkstra(int[] gates, int[] summits){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        for(int i=0;i<gates.length;i++){
            pq.offer(new Node(gates[i], 0));
            d[gates[i]] = 0;
        }
        
        while(!pq.isEmpty()){
            Node nownode = pq.poll();
            int nowindex = nownode.index;
            int nowdistance = nownode.distance;
            
            if(d[nowindex] < nowdistance)
                continue;
            
           if(summitshashset.contains(nowindex))
               continue;
            // boolean flag = false;
            // for(int i=0;i<summits.length;i++){
            //     if(summits[i] == nowindex){
            //         flag = true;
            //     }
            // }
            // if(flag == true) continue;
            
            //여기서 이제 
            for(int i=0;i<graph.get(nowindex).size();i++){
                int cost = Math.max(d[nowindex], graph.get(nowindex).get(i).distance);
                if( d[graph.get(nowindex).get(i).index] > cost){
                    d[graph.get(nowindex).get(i).index] = cost;
                    pq.offer(new Node(graph.get(nowindex).get(i).index, cost));
                }
            }   
        }
    }
    
    
}

class Node implements Comparable<Node>{
    int index;
    int distance;
    public Node(){
        
    }
    public Node(int index, int distance){
        this.index = index;
        this.distance = distance;
    }
    
    public int compareTo(Node other){
        if(this.distance > other.distance){
            return 1;
        }
        return 0;
    }
}

 

그래프를 애초에 완전양방향이 아닌, 정상에서는 단방향으로 만든 코드

import java.io.*;
import java.util.*;
import java.util.Map.*;
class Solution {

    public ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    public int[] d;
    public Set<Integer> gateshashset = new HashSet<Integer>();
    public Set<Integer> summitshashset = new HashSet<Integer>();    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        for(int a : summits){
            summitshashset.add(a);
        }
        for(int a : gates){
            gateshashset.add(a);
        }
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        } 
        d = new int[n+1];
        Arrays.fill(d, Integer.MAX_VALUE);

        for(int i=0;i<paths.length;i++){
            int startnode = paths[i][0];
            int endnode = paths[i][1];
            int distance = paths[i][2];


//startnode가 gates가 아니고, endnode가 summit이 아닐때
            if( gateshashset.contains(startnode) || summitshashset.contains(endnode)) {
                graph.get(startnode).add(new Node(endnode, distance));
            }
            //endnode가 gates가 아니고 startnode가 summit이 아닐때
            else if( gateshashset.contains(endnode) || summitshashset.contains(startnode)){
                graph.get(endnode).add(new Node(startnode, distance));
            }else{
            //양방향 노드이니 두개 다 넣습니다. 
            graph.get(startnode).add(new Node(endnode, distance));
            graph.get(endnode).add(new Node(startnode, distance));
            }
            //이렇게 하면 마지막 테스트케이스 최앆의 경우 산봉우리일때 아예 멈추도록한다는것자체가 프로그래멩 무리가 가므로 여기서 걸러줍니다

        }

        //그래프 잘 만들었는지 테스트
//        for(int i=1;i<graph.size();i++){
  //          for(int j=0;j<graph.get(i).size();j++){
    //            System.out.print(" "+graph.get(i).get(j).index+" "+graph.get(i).get(j).distance);
      //      }
        //  System.out.println();
    // }

       dijkstra(gates, summits);

//        for(int a : d){
//            System.out.println(a);
//        }


        int[] answer = {0, Integer.MAX_VALUE};

        for(int i=0;i<summits.length;i++){
            if(d[summits[i]] < answer[1]){
                answer[0] = summits[i];
                answer[1] = d[summits[i]];
            }else if(d[summits[i]] == answer[1] && summits[i] < answer[0]){
                answer[0] = summits[i];
            }    
        }


        return answer;
    }


    public void dijkstra(int[] gates, int[] summits){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        //출입구들은 모두 0으로 설정하여 시작점으로 잡아주고 다익스트라를 시작합니다.

        for(int i=0;i<gates.length;i++){
            pq.offer(new Node(gates[i], 0));
            d[gates[i]] = 0;
        }

        while(!pq.isEmpty()){
            Node temp = pq.poll();
            int now = temp.index;
            int distance = temp.distance;

            if(d[temp.index] < temp.distance){
                continue;
            }

            //노드가 산봉우리를 지나도 굳이 돌필요없으므로 거기서 그만.
            //if(summitshashset.contains(now))
            //    continue;

            //각 경로마다의 intensity는 최대값을 구해주고,
            //진짜 d[]는 최솟값을 구하는 것입니다.
            //말이 어렵지만 이렇게 표헌.
            for(int i=0;i<graph.get(now).size();i++){   
                int cost = Math.max(d[now], graph.get(now).get(i).distance);
                if( d[graph.get(now).get(i).index] > cost ){
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }                    
            }
        }
    }


}

class Node implements Comparable<Node>{
    int index;
    int distance;
    public Node(int index, int distance){
        this.index = index;
        this.distance = distance;
    }

    public int compareTo(Node other){
        if(this.distance < other.distance){
            return 1;        
        }
        return 0;
    }

}

 

 

두번쨰 풀어본코드

import java.util.*;
class Solution {
    ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    int[] d;
    int[] Gates;
    int[] Summits;
    HashSet<Integer> summits_hashset = new HashSet<>();
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        Gates = gates;
        Summits = summits;
        for(int a : summits)
            summits_hashset.add(a);
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }
        d = new int[n+1];
        Arrays.fill(d, Integer.MAX_VALUE);
        
        for(int i=0;i<paths.length;i++){
            int startnode = paths[i][0];
            int endnode = paths[i][1];
            int distance = paths[i][2];
            
            graph.get(startnode).add(new Node(endnode, distance));
            graph.get(endnode).add(new Node(startnode, distance));
        }
        
        
        dijkstra();
        
        
        int[] answer = {0, Integer.MAX_VALUE};
        // for(int i=0;i<=n;i++){
        //     System.out.print(" "+d[i]);
        // }
        // System.out.println();
        for(int i=0;i<summits.length;i++){
            if(d[summits[i]] < answer[1]){
                answer[0] = summits[i];
                answer[1] = d[summits[i]];
            }else if( d[summits[i]] == answer[1] && summits[i] < answer[0]){
                answer[0] = summits[i];
            }
        }
        
        return answer;
    }
    
    void dijkstra(){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        //출입구들은 모두 0으로 설정하여 시작점으로 잡아주고 다익스트라를 시작합니다.
        for(int i=0;i<Gates.length;i++){
            pq.offer(new Node(Gates[i], 0));
            d[Gates[i]] = 0;
        }
        
        while(!pq.isEmpty()){
            // for(int i=0;i<=d.length-1;i++){
            //     System.out.print(" "+d[i]);
            // }
            // System.out.println();
            Node temp = pq.poll();
            int now = temp.index;
            int distance = temp.distance;
            
            if(d[now] < distance) continue;
            
            if(summits_hashset.contains(now))
                continue;
            
            
            //각 경로마다의 intensity는 최대값을 구해주고, 
            //진짜 d[]는 최솟값을 구하는 것입니다.
            for(int i=0;i<graph.get(now).size();i++){
                int cost = Math.max(d[now], graph.get(now).get(i).distance);
                if(d[graph.get(now).get(i).index] > cost){
                    d[graph.get(now).get(i).index] = cost;
                     pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
    }
    
    class Node implements Comparable<Node>{
        int index;
        int distance;
        public Node(int index, int distance){
            this.index = index;
            this.distance = distance;
        }
        
        public int compareTo(Node other){
            //우선순위큐, 거리가 가까운 것들부터 먼저 빼냅니다.
            //최소힙. 가장 값이 작은 원소, 최단경로 알고리즘
            //시작노드로부터 거리가 짧은 노드 순서대로 큐에서 나올 수 있도록 
            
            if(this.distance < other.distance){
                return -1;
            }else{
                return 0;
            }
        }
    }
}