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

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr)

어떻게 생각하고 문제를 풀었는가?

지점 k에서 A와 B가 택시를 따로 이용하여 목표지점으로 가는 경우 s->k까지의 최소비용 + k->A까지의 최소비용 + k->B까지의 최소비용으로 계산할 수 있습니다.

택시요금은 방향에 따라 달라지지 않습니다. 따라서 s에서 시작하여 각 지점까지의 최소비용, A에서 시작하여 각 지점까지의 최소 비용, B에서 시작하여 각 지점까지의 최소 비용을 미리 계산한 후 모든 k에 대한 비용 중 최소 값을 찾음으로서 전체 최소요금을 구할 수 있습니다.

코드

import java.util.*;
class Solution {
    final int MAX = 20000001;
    int[][] lines;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        lines = new int[n][n];
        for(int[] fare : fares){
            lines[fare[0]-1][fare[1]-1] = fare[2];
            lines[fare[1]-1][fare[0]-1] = fare[2];
        }
        int[] dijkS = dijkstra(s-1,n);
        int[] dijkA = dijkstra(a-1,n);
        int[] dijkB = dijkstra(b-1,n);
        int answer=MAX;
        for(int i=0;i<n;i++){
            int cost =dijkS[i]+dijkA[i]+dijkB[i]; 
            if(answer>cost) answer = cost;
        }
        return answer;
    }
    public int[] dijkstra(int start,int n){
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)->x[1]-y[1]);
        pq.add(new int[]{start,0});
        int[] result = new int[n];
        Arrays.fill(result,MAX);
        result[start]=0;
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            if(curr[1] > result[curr[0]]) continue;   //방문하는 의미가 없음
            for(int i=0;i<n;i++){
                int cost = lines[curr[0]][i]+result[curr[0]];
                if(lines[curr[0]][i]>0 && result[i]>cost){
                    result[i] = cost;
                    pq.offer(new int[]{i,cost});
                } 
            }    
        }
        return result;
    }
} 

dijkstra 알고리즘을 이용하여 시작 위치에서 각 지점까지 가는데 드는 최소 비용을 계산하였습니다.

dijkstra 알고리즘은 비용이 최소인 노선을 사용하여 지점을 방문한 후 지점에 도착하는데 드는 비용을 저장함으로서 구현할 수 있습니다.

S, A, B에서 시작하는 dijkstra 계산결과를 저장한 후, 최소 값이 되는 k를 찾아 비용을 반환합니다.