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

https://school.programmers.co.kr/learn/courses/30/lessons/72413?language=java

프로그래머스

 

 

Idea

오랜만에 AI 추천 문제에 도전했다. 가중치가 있는 경로 찾기 문제여서 다익스트라 개념을 가장 먼저 떠올렸다.

 

 

Code

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int distS[] = dijkstra(n, s, fares);
        int distA[] = dijkstra(n, a, fares);
        int distB[] = dijkstra(n, b, fares);
        
        int minFare = distS[a] + distA[b];
        
        for (int i = 1; i <= n; i++) {
            int fare = distS[i] + distA[i] + distB[i];
            minFare = Math.min(minFare, fare);
        }
        return minFare;
    }
    
    private int[] dijkstra(int n, int s, int[][] fares) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[s] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{s, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int fare = current[1];
            
            if (fare > distance[node]) {
                continue;
            }
            
            for (int[] f : fares) {
                int u = f[0];
                int v = f[1];
                int w = f[2];
            
                if (u == node || v == node) {
                    int nextNode = (u == node) ? v : u;
                    int nextFare = fare + w;

                    if (nextFare < distance[nextNode]) {
                        distance[nextNode] = nextFare;
                        pq.offer(new int[]{nextNode, nextFare});
                    }
                }
            }
        }
        return distance;
    }
}