[카카오 기출 문제]합승 택시 요금- 레벨 3, 다익스트라 + 완전탐색 + 아이디어 + 그래프

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

프로그래머스

이 문제는 다익스트라를 이용하여 최단거리를 구하여 푸는 문제입니다.

 

효율성점수가 있는 문제이기에 역시나 직관적으로 풀경우 시간초과가 납니다.

 

저 같은경우 직관적으로 풀었더니 시간초과가 났습니다.

 

기억해야할점들

 

이 부분때문에 시간초과가 납니다.

문제의 조건대로, 시작인덱스에서 환승지점 + 환승지점에서 a로 + 환승지점에서 b로 구현했습니다.

dijkstra(s, i) : 시작인덱스 s에서 i 로 의 최단거리

dijkstra(i, a) : 시작인덱스 i에서 a로의 최단거리

dijkstra(i, b) : 시작인덱스 i에서 b로의 최단거리

를 사용하여 구하면 이 문제는 일종의 완전탐색 문제가 되어 버립니다. 이렇게 하면 시간초과가 납니다.

for(int i=1;i<=n;i++){
    answer = Math.min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b));
}

 

시간초과가 난 코드

import java.io.*;
import java.util.*;
import java.util.Map.*;
class Solution {
    ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    int N = 0;
    int[] d;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 100000 * n + 1;
        N = n;
        d = new int[N+1];
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }
        
        for(int i=0;i<fares.length;i++){
            int s_ = fares[i][0];
            int e_ = fares[i][1];
            int d_ = fares[i][2];
            graph.get(s_).add(new Node(e_, d_));
            graph.get(e_).add(new Node(s_, d_));
        }
        
        for(int i=1;i<=n;i++){
            answer = Math.min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b));
        }
        
        return answer;
    }
    
    //다익스트라
    public int dijkstra(int start, int dest){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.offer(new Node(start, 0));
        // Arrays.fill(d, 100000*N + 1);
        Arrays.fill(d, Integer.MAX_VALUE);
        d[start] = 0; 
        
        while(!pq.isEmpty()){
            Node curr = pq.poll();
            int now = curr.index;
            int distance = curr.distance;
            if(d[now] < distance) continue;
            
            for(int i=0;i<graph.get(now).size();i++){
                int cost = d[now] + graph.get(now).get(i).distance;
                if( cost < d[graph.get(now).get(i).index]){
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
        
        return d[dest];
    }
        
}

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;
    }
}

 

 

위의 완전탐색 다익스트라와 달리,

dijkstra(s)  s에서 모든 경로로 갔을때의 최단거리 배열 distS

dijkstra(a) a에서 모든 경로로 갔을떄의 최단거리 배열 distA

a 도착지를 도착지가 아닌 출발점으로 보아  갈수있는 가장 빠른방법

dijkstra(b) b에서 모든 경로로 갔을때의 최단거리 배열 distB

b 도착지를 도착지가 아닌 출발점으로 보아 갈 수 있는 가장 빠른 방법

 

그리고 각 i, 즉 환승지점을 하나씩 돌면서 가장 빠른 지점을 찾는 방법입니다.

int[] distS = dijkstra(s, n);
int[] distA = dijkstra(a, n);
int[] distB = dijkstra(b, n);

for(int i=1; i<=n; i++){
    if(minfare > distS[i] + distA[i] + distB[i]){
        minfare = distS[i] + distA[i] + distB[i];
    }
}

위의 시간초과의 경우 총 n번의 다익스트라 탐색을 하지만, 이번 코드같은경우는

무조건 3번의 다익스트라 탐색을하여 O(3 Log 3)의 속도입니다.

 

통과한 코드

int[] distS = dijkstra(s);
int[] distA = dijkstra(a);
int[] distB = dijkstra(b);

for(int i=1; i<=n; i++){
    if(minfare > distS[i] + distA[i] + distB[i]){
        minfare = distS[i] + distA[i] + distB[i];
    }
}

 

 

시간초과가 나지 않은 코드입니다.

import java.io.*;
import java.util.*;
import java.util.Map.*;
class Solution {
    ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    int minfare=0;
    int N = 0;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        N= n;
        minfare = 100000 * n + 1;
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }

        for(int i=0;i<fares.length;i++){
            int s_ = fares[i][0];
            int e_ = fares[i][1];
            int d_ = fares[i][2];
            graph.get(s_).add(new Node(e_, d_));
            graph.get(e_).add(new Node(s_, d_));
        }
        // dijkstra(s, a, b)

        int[] distS = dijkstra(s);
        int[] distA = dijkstra(a);
        int[] distB = dijkstra(b);

        for(int i=1; i<=n; i++){
            if(minfare > distS[i] + distA[i] + distB[i]){
                minfare = distS[i] + distA[i] + distB[i];
            }
        }
        return minfare;
    }

    //다익스트라
    public int[] dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.offer(new Node(start, 0));
        int[] d = new int[N+1];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[start] = 0; 

        while(!pq.isEmpty()){
            Node curr = pq.poll();
            int now = curr.index;
            int distance = curr.distance;
            if(d[now] < distance) continue;

            for(int i=0;i<graph.get(now).size();i++){
                int cost = d[now] + graph.get(now).get(i).distance;
                if( cost < d[graph.get(now).get(i).index]){
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
        return d;
    }

}

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.util.*;
class Solution {
    ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    int[] d;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        d = new int[n+1];

        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }
        
        for(int i=0;i<fares.length;i++){
            int start = fares[i][0];
            int end = fares[i][1];
            int dist = fares[i][2];   
            graph.get(end).add(new Node(start, dist));
            graph.get(start).add(new Node(end, dist));
            
        }
        
        int[] s_dist = new int[n+1];
        int[] a_dist = new int[n+1];
        int[] b_dist = new int[n+1];
        
        dijkstra(s);
        for(int i=0;i<d.length;i++){
            s_dist[i] = d[i];
            System.out.print(" "+d[i]);
        }
        System.out.println();
        
        dijkstra(a);
        for(int i=0;i<d.length;i++){
            a_dist[i] = d[i];
            System.out.print(" "+d[i]);
        }
        System.out.println();
        
        dijkstra(b);
        for(int i=0;i<d.length;i++){
            b_dist[i] = d[i];
            System.out.print(" "+d[i]);
        }
        System.out.println();
        
        int summin = Integer.MAX_VALUE;
        for(int i=0;i<d.length;i++){
            int s_value = s_dist[i];
            int a_value = a_dist[i];
            int b_value = b_dist[i];
            summin = Math.min(summin, s_value + a_value + b_value);
        }
        
        int answer = summin;
        return answer;
    }
    
    void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        Arrays.fill(d, Integer.MAX_VALUE);
        d[start] = 0;
        pq.offer(new Node(start, 0));
        
        while(!pq.isEmpty()){
            Node temp = pq.poll();
            int now = temp.index;
            int dist = temp.distance;
            
            if(d[now] < dist){
                continue;
            }
            
            for(int i=0;i<graph.get(now).size();i++){
                int cost = d[now] + graph.get(now).get(i).distance;
                // System.out.println("cost: "+cost);
                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(){
            
        }
        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 1;
        }
    }
}