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

문제 합승 택시 요금

문제 접근

1. 노드별 최소 비용으로 최단거리로 이동해야되므로 최단경로탐색알고리즘을 이용한다. 즉 다익스트라를 사용
2. 출발 지점 -> 특정 지점 X -> 도착 지점으로 이동하는 경우와 출발 지점 -> 도착 지점 경우 중 최소 비용을 탐색
3. 출발 지점, 도착 지점(A,B)에서 모든 지점별로 최소 비용을 탐색
4. 출발 지점에서 1 ~ N까지 지점 중 환승구역을 거쳐서 도착 지점까지 걸어가는 비용 중에 최소 비용을 확인

import java.util.*;

class Solution {
    int maxV = 20000001;
    ArrayList<Node> []graph;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        graph = new ArrayList[n+1];
        
        for(int i=0;i<=n;i++)
        {
            graph[i] = new ArrayList<>();
        }
        
        //양방향으로 연결
        for(int i =0;i<fares.length;i++)
        {
            graph[fares[i][0]].add(new Node(fares[i][1],fares[i][2]));
            graph[fares[i][1]].add(new Node(fares[i][0],fares[i][2]));
        }
        
        //시작지점,a의 지점, b의 지점에서의 모든 지점들로 이동시 최소비용
        int []startS = dijkstra(s,n);
        int []startA = dijkstra(a,n);
        int []startB = dijkstra(b,n);
        
        answer = maxV;
        for(int i = 1; i<=n;i++)
        {
            answer = Math.min(answer, startS[i]+startA[i]+startB[i]);
        }
        
        return answer;
    }
    
    
    public int[] dijkstra(int start,int n)
    {
        
        int dist[] = new int[n+1]; //start -> 지점별 거리
        Arrays.fill(dist,maxV);
        
        PriorityQueue <Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start,0));
        dist[start] = 0;
        
        while(!pq.isEmpty())
        {
            Node cnt = pq.poll();
            
            for(Node node : graph[cnt.x])
            {
                if(dist[node.x] > node.dist + cnt.dist)
                {
                    dist[node.x] = node.dist + cnt.dist;
                    pq.offer(new Node(node.x,node.dist + cnt.dist));
                }
            }
        }
        
        return dist;
    }
    
    class Node implements Comparable<Node>
    {
        int x;
        int dist;
        
        public Node(int x, int dist)
        {
            this.x = x;
            this.dist = dist;
        }
        
        @Override
        public int compareTo(Node e){
            return this.dist - e.dist;
        }
    }
}

참고 사이트

https://m.blog.naver.com/ndb796/221234424646
https://dev-jaguar.tistory.com/entry/Programmers%ED%95%A9%EC%8A%B9%ED%83%9D%EC%8B%9C%EC%9A%94%EA%B8%88