[프로그래머스] 합승 택시 요금(JAVA), 다익스트라, 2021 KAKAO BLIND RECRUITMENT

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

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

풀이

다익스트라를 이용해 최단거리를 구하는 문제다. 주의할 점은 A와 B가 합승을 어느 정점까지 하는 것이 최소비용이 될 지 구하는 것인데, 다익스트라를 3번 (합승할 경우, A 혼자 탈 경우, B 혼자 탈 경우) 하면 해결되는 문제다.

• 출발지점 s로부터 모든 정점까지의 최소비용을 저장하는 together
• A의 도착지점 a로부터 모든 정점까지의 최소비용을 저장하는 aloneA
• B의 도착지점 b로부터 모든 정점까지의 최소비용을 저장하는 aloneB

위와 같이 세 번의 다익스트라를 수행할 경우, together[i]+aloneA[i]+aloneB[i] 은 i 정점까지 합승한 후 각자 택시를 타고 집으로 갔을 경우의 비용을 뜻한다.

문제에서는 정점이 1부터 n 까지 임을 주의하여 배열과 인접리스트를 생성한다.
나는 0부터 n-1 까지의 크기가 n인 배열, 리스트로 풀이하였다.

---

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Edge implements Comparable<Edge> {
    int vex, cost;

    public Edge(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}

class Solution {
    ArrayList<ArrayList<Edge>> graph = new ArrayList<>();

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] o : fares) {
            graph.get(o[0]-1).add(new Edge(o[1]-1, o[2]));
            graph.get(o[1]-1).add(new Edge(o[0]-1, o[2]));
        }
        int[] together = dijkstra(s - 1, new int[n]);
        int[] aloneA = dijkstra(a - 1, new int[n]);
        int[] aloneB = dijkstra(b - 1, new int[n]);

        for (int i = 0; i < n; i++) {
            if (together[i] == Integer.MAX_VALUE || aloneA[i] == Integer.MAX_VALUE || aloneB[i] == Integer.MAX_VALUE)
                continue;
            answer = Math.min(answer, together[i] + aloneA[i] + aloneB[i]);
        }

        return answer;
    }

    public int[] dijkstra(int start, int[] dis) {
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.offer(new Edge(start, 0));
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;
        while (!pQ.isEmpty()) {
            Edge tmp = pQ.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            if (nowCost > dis[now]) continue;
            for (Edge o : graph.get(now)) {
                if (dis[o.vex] > nowCost + o.cost) {
                    dis[o.vex] = nowCost + o.cost;
                    pQ.offer(new Edge(o.vex, dis[o.vex]));
                }
            }
        }
        return dis;
    }

}