[JAVA] 2021 KAKAO BLIND RECRUITMENT 【합승 택시 요금】

---

문제에서 요구하는 답을 간략하게 표현하면, 

 

(출발지점 → 경유지점) 요금 + (경유지점 → 무지 목적지) 요금 + (경유지점 → 어피치 지점) 요금 = 최종 요금

 

위 식으로부터 구해진 최종 요금의 최솟값을 답으로 출력하면 된다.

 

처음에 푼 방식은 시간 초과가 계속 발생했는데

 

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

위와 같이, 다익스트라 알고리즘을 루프문마다 3번씩 사용하고 있었다.

 

 

다시 생각해보니,

 

출발지점 → 경유지점 요금 정보는 다익스트라 알고리즘을 한번만 수행해서 구할 수 있고

 

(경유지점 → 무지 목적지) 요금 + (경유지점 → 어피치 지점)요금 역시 다익스트라 알고리즘 한번 수행하면 두 정보를 얻을 수 있다.

 

다만 경유 지점 마다 다 구해봐야 하기 때문에, for문을 통해서 경유지점 별 요금 정보를 구해야한다.

 

따라서 아래와 같이 로직을 변경하니, 다익스트라 알고리즘 사용 횟수를 줄일 수 있었고 시간제한 초과 없이 통과할 수 있었다.

        int[] result1 = dijk(s);
        
        for(int i=1;i<=n;i++){
            int[] result2 = dijk(i);
            answer = Math.min(answer,result1[i-1]+result2[a-1]+result2[b-1]);
        }

---

 

import java.util.*;
class Solution {
    final int MAX = 20000001;
    int n;
    int[][] g;
    int[] dist;
    boolean[] checked;
    PriorityQueue<int[]> pq;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = MAX;
        setUp(n,fares);
        
        int[] result1 = dijk(s);
        
        for(int i=1;i<=n;i++){
            int[] result2 = dijk(i);
            answer = Math.min(answer,result1[i-1]+result2[a-1]+result2[b-1]);
        }
        return answer;
    }
    int[] dijk(int start){
        pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
        dist = new int[n];
        checked = new boolean[n];
        Arrays.fill(dist,MAX);
        dist[start-1] = 0;
        pq.offer(new int[]{dist[start-1],start-1});
        while(!pq.isEmpty()){
            int[] info = pq.poll();
            int u = info[1];
            if(checked[u]){
                continue;
            }
            checked[u]=true;
            for(int v=0;v<n;v++){
                if(dist[v]>dist[u]+g[u][v]){
                    dist[v]=dist[u]+g[u][v];
                    pq.offer(new int[]{dist[v],v});
                }
            }
        }
        return dist;
        
    }
    void setUp(int n,int[][] fares){
        this.n=n;
        g = new int[n][n];
        for(int r=0;r<n;r++){
            for(int c=0;c<n;c++){
                if(r==c){
                    g[r][c]=0;
                }else{
                    g[r][c]=MAX;
                }
            }
        }
        
        
        for(int r=0;r<fares.length;r++){
            int[] fare = fares[r];
            for(int c=0;c<n;c++){
                g[fare[0]-1][fare[1]-1]=fare[2];
                g[fare[1]-1][fare[0]-1]=fare[2];
            }
        }
        
    }
}