[프로그래머스] 합승 택시 요금 - java

 

 

나의 풀이

import java.util.*;

class Solution {

    static final int MAX = 20000001;
    static ArrayList<Node>[] graph;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = MAX;
        graph = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            graph[i] = new ArrayList<Node>();
        }

        for(int[] fare : fares){
            graph[fare[0]].add(new Node(fare[1], fare[2]));
            graph[fare[1]].add(new Node(fare[0], fare[2]));
        }

        int[] startA = dijkstra(a,n);
        int[] startB = dijkstra(b,n);
        int[] start = dijkstra(s,n);

        for(int i=1; i<=n; i++){ // S->i까지 경유하고 i->a & i->b 까지 따로간다.
            answer = Math.min(answer, start[i] + startA[i] + startB[i]);
        }

        return answer;
    }

    public int[] dijkstra(int start, int n){
        int[] dist = new int[n+1]; // dist[i] : start->i 까지의 거리
        Arrays.fill(dist, MAX);
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start] = 0;

        while(!q.isEmpty()){
            Node now = q.poll();
            for(Node node : graph[now.x]){
                if (dist[node.x] > now.dist + node.dist){
                    dist[node.x] = now.dist + node.dist;
                    q.add(new Node(node.x, now.dist + node.dist));
                }
            }
        }
        return dist;
    }

    class Node implements Comparable<Node>{
        int x;
        int dist;

        Node(int x, int dist){
            this.x = x;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node e){
            return this.dist - e.dist;
        }
    }
}

 

s->x 지점까지 합승한다고 가정하자.

그렇다면 (s->x 까지의 거리) + (x->a까지의 거리) + (x->b까지의 거리) 가 전체 거리의 합이 될 것이다.

즉, x지점을 1~N까지 대입해봤을 때의 최소값이 answer 이 됨을 알 수 있다.

 

 

s->x / x->a / x->b 까지의 거리를 구하기 위해서는 3번의 다익스트라를 실행해야 한다.

이때 모든 경로는 방향이 없으므로, x->a 는 a->x와 동일하다. 따라서 a,b를 출발점으로 하여 모든경로까지의 거리를 구하면 된다.

 

s를 시작점으로 모든 경로까지의 최단 경로 => int[] start

a를 시작점으로 모든 경로까지의 최단 경로 => int[] startA 

b를 시작점으로 모든 경로까지의 최단 경로 => int[] startB