[프로그래머스/JAVA] 합승 택시 요금

문제 보러가기

 

[코드]

 

import java.util.*; class Solution {     List<List<Node>> graph = new ArrayList<>(); //노드 간의 관계 정보     int max = 100000 * 200 + 1;     public int solution(int n, int s, int a, int b, int[][] fares) {         int answer = Integer.MAX_VALUE;         int[] startA = new int[n + 1];         int[] startB = new int[n + 1];         int[] start = new int[n + 1];         for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());         for (int[] fare : fares) { //노드 간의 관계 입력             graph.get(fare[1]).add(new Node(fare[0], fare[2]));             graph.get(fare[0]).add(new Node(fare[1], fare[2]));         }         Arrays.fill(startA, max); //노드 비용 초기화         Arrays.fill(startB, max);         Arrays.fill(start, max);         Daik(a, startA); // a에서 각 노드로 향하는 비용 구하기         Daik(b, startB);         Daik(s, start);         for (int i = 1; i <= n; i++) { // i 노드까지 같이 합승하고, i 노드부터 각자의 위치로 갈 때 최소값 구하기             answer = Math.min(answer, startA[i] + startB[i] + start[i]);         }         return answer;     }     public void Daik(int start, int[] cost) {         PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost)); //비용 순으로 정렬         pq.add(new Node(start, 0));         cost[start] = 0;         while (!pq.isEmpty()) {             Node now = pq.poll();             int nowIndex = now.node;             int nowCost = now.cost;             if (nowCost > cost[nowIndex]) continue; //가져온 비용이 기존의 비용보다 크다면 구할 필요가 없다             List<Node> edges = graph.get(nowIndex);             for (Node edge : edges) {                 int costs = edge.cost + cost[nowIndex];                 if (costs < cost[edge.node]) { //새로운 비용이 기존의 비용보다 작다면 실                     cost[edge.node] = costs;                     pq.add(new Node(edge.node, costs));                 }             }         }     } } class Node {     int node;     int cost;     Node(int node, int cost) {         this.node = node;         this.cost = cost;     } }