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

문제 보기

사용한 것

• 최소 비용을 구하기 위한 다익스트라 알고리즘
• 다익스트라 구현을 위한 PriorityQueue

풀이 방법

• fares로 인접 행렬 생성
• 출발 지점부터 모든 정점 까지 최소 비용을 다익스트라로 구하기 -> together
• 정점을 for문으로 돌며 해당 정점부터 모든 정점까지 최소 비용을 다익스트라로 구하기 -> alone
• together[i] + alone[a - 1] + alone[b - 1]로 어피치와 무지의 총 택시비를 계산하여 최솟 값 구하기
• 즉, 출발 지점부터 함께 택시 타고간 정점 까지의 비용 + 어피치 혼자 택시탄 비용 + 무지 혼자 택시탄 비용을 계산하는 것

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {

    int N;
    int E;
    int[][] matrix;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        N = n;
        E = fares.length;
        matrix = new int[n][n];

        for (int i = 0; i < E; i++) {
            int u = fares[i][0] - 1;
            int v = fares[i][1] - 1;
            int cost = fares[i][2];
            matrix[u][v] = cost;
            matrix[v][u] = cost;
        }

        int[] together = dijkstra(s - 1);
        int minCost = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++) {
            int[] alone = dijkstra(i);
            int cost = together[i] + alone[a - 1] + alone[b - 1];
            if(cost < minCost) {
                minCost = cost;
            }
        }

        return minCost;
    }

    public int[] dijkstra(int start) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        boolean[] visited = new boolean[N];
        int[] distance = new int[N];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        pq.add(new int[] {0, start});

        while (!pq.isEmpty()) {
            int[] cur = pq.remove();
            int u = cur[1];
            if (visited[u]) {
                continue;
            }

            visited[u] = true;
            for (int v = 0; v < N; v++) {
                if(matrix[u][v] == 0) {
                    continue;
                }
                if (distance[u] + matrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + matrix[u][v];
                    pq.add(new int[]{distance[v], v});
                }
            }
        }

        return distance;
    }
}