프로그래머스 [Lv. 3] 합승 택시 요금 {언어 : Java} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

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

class Solution {
    class Node {
        int index;
        int cost;

        Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        List<List<Node>> adjL = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjL.add(new ArrayList<>());
        }
        for (int[] fare : fares) {
            adjL.get(fare[0]).add(new Node(fare[1], fare[2]));
            adjL.get(fare[1]).add(new Node(fare[0], fare[2]));
        }

        int[] distFromS = dijkstra(n, s, adjL);
        int[] distFromA = dijkstra(n, a, adjL);
        int[] distFromB = dijkstra(n, b, adjL);

        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (distFromS[i] != Integer.MAX_VALUE && distFromA[i] != Integer.MAX_VALUE && distFromB[i] != Integer.MAX_VALUE) {
                minCost = Math.min(minCost, distFromS[i] + distFromA[i] + distFromB[i]);
            }
        }

        return minCost;
    }

    private int[] dijkstra(int n, int start, List<List<Node>> adjL) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentIndex = current.index;
            int currentCost = current.cost;

            if (currentCost > dist[currentIndex]) {
                continue;
            }

            for (Node neighbor : adjL.get(currentIndex)) {
                int newDist = currentCost + neighbor.cost;
                if (newDist < dist[neighbor.index]) {
                    dist[neighbor.index] = newDist;
                    pq.add(new Node(neighbor.index, newDist));
                }
            }
        }

        return dist;
    }
}

풀이 방법

 

1. 다익스트라 알고리즘을 사용하여 최단 거리 계산:
   1. dijkstra 메서드는 주어진 시작점에서 모든 다른 지점까지의 최단 거리를 계산한다.
   2. 우선순위 큐를 사용하여 효율적으로 최단 거리를 업데이트한다.
2. 세 번의 다익스트라 실행:
   1. 출발지점 s에서 모든 지점까지의 최단 거리 distFromS를 계산한다.
   2. a에서 모든 지점까지의 최단 거리 distFromA를 계산한다.
   3. b에서 모든 지점까지의 최단 거리 distFromB를 계산한다.
3. 최소 비용 계산:
   1. s에서 합승 지점 i까지의 비용, i에서 a까지의 비용, i에서 b까지의 비용을 모두 합산하여 최소 비용을 찾으면 끝!

 

 

느낀점

• PriorityQueue, Comparator, ArrayList, List<List<Node>> 등 다양한 문법을 배웠다.
• 솔직히 파이썬으로는 풀 수 있을 것 같은데 자바스크립트로는 어떻게 풀지...?