[프로그래머스] 합승 택시 요금 (Java)

문제

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

코딩테스트 연습 - 합승 택시 요금

 

풀이

Dijkstra로 각 정점의 최단 거리를 찾는다

S지점에서 X라는 지점에 도착해서 X->A, X->B 로 갈라진다. 

즉, S->X + X->A + X->B 의 최단거리를 찾으면 된다. 

플로이드 와샬 알고리즘으로 시도했지만, 시간초과가 발생해서 다익스트라로 다시 풀었다. 

S, A, B 에 대해 각각 모든 정점에 대한 최단 거리를 다익스트라 알고리즘으로 구한 후, 

S->X + X->A + X->B 의 min값을 찾는다.

 

소스코드

import java.util.*;

class Edge {
    int to; 
    int dist;    
    public Edge(int to, int dist){
        this.to = to;
        this.dist = dist;
    }
}

class Info implements Comparable<Info>{
    int node;
    int dist;   
    public Info(int node, int dist){
        this.node = node;
        this.dist = dist;
    }
    
    @Override
    public int compareTo(Info i){
        return this.dist - i.dist;
    }
}

class Solution {
    public int n;
    public ArrayList<Edge>[] edges;
    public int solution(int n, int s, int a, int b, int[][] fares) {   
        int answer = 0;
        this.n = n;
        
        // 1. Set EdgeList
        this.edges = new ArrayList[n+1];
        for(int i = 0; i <= n; i++) edges[i] = new ArrayList<Edge>();
        for(int i = 0; i < fares.length; i++) {
            int n1 = fares[i][0];
            int n2 = fares[i][1];
            int dist = fares[i][2];
            edges[n1].add(new Edge(n2, dist));
            edges[n2].add(new Edge(n1, dist));
        }
        
        int[] distS = dijkstra(s);
        int[] distA = dijkstra(a);
        int[] distB = dijkstra(b);
        
        // A와 B가 갈라지는 지점을 찾는 것임. 
        // S ~ 갈라지는 지점
        // 갈라지는 지점 ~ A
        // 갈라지는 지점 ~ B
        // S, A, B에 대해 모든 정점에 대한 최단 경로를 찾은 다음에 
        // 세 곳과의 거리를 합했을 때 가장 최소가 되는 지점을 찾는 것.
        
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            if(min > distS[i] + distA[i] + distB[i]){
                min = distS[i] + distA[i] + distB[i];
            }
        }
            
        return min;
    }
    
    public int[] dijkstra(int s){
        // 2. set Dists
        int[] dist = new int[n+1];
        for(int i = 0; i <= n; i++) dist[i] = Integer.MAX_VALUE;
        
        // 3. set PriorityQueue
        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        
        // 4. offer startNode
        dist[s] = 0;
        pq.offer(new Info(s, dist[s]));
 
        
        // 5. update dist
        while(!pq.isEmpty()){
            Info info = pq.poll();
            if(info.dist > dist[info.node]) continue;
            for(Edge adj : edges[info.node]){
                if(adj.dist + dist[info.node] > dist[adj.to]) continue;
                dist[adj.to] = adj.dist + dist[info.node];
                pq.offer(new Info(adj.to, dist[adj.to]));
            } 
        }
        
        return dist;
    }
}