[pro] 프로그래머스 level3 72413 합승 택시 요금 (Java) - 다익스트라

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

[풀이]

출발 지점과 도착지점이 주어지고, 노드들 사이에 양수 가중치가 있기 때문에 다익스트라를 생각해볼 수 있다.

s에서 출발해서 a, b 지점 모두에 최저 요금으로 도착을 해야 한다. 합승을 할 수 있기 때문에 예시에서처럼 s->x 지점까지 함께 가고, x->a, x->b 지점으로 이동하는 형태가 될 것이다. 

이는 다음 4가지 경우의 수를 모두 충족한다.

1) 처음부터 따로 이동하는 경우 == x가 s인 경우. s->s + s->a + s->b

2) x지점이 함께 간 후 따로 이동하는 경우. s->x + x->a + x->b. 이때 x는 s, a, b가 아니다.

3) x지점이 a인 경우. s->a + a->a + a->b.

4) x지점이 b인 경우. s->b + a->b + b->b.

 

따라서 출발점이 s, a, b인 경우 모든 지점까지의 최단 거리(최저 요금)를 다익스트라를 이용하여 구한 후, 모든 x 지점에 대해서 s->x + x->a + x->b 가 최저인 경우를 구하도록 한다.

 

[코드]

 

import java.util.*;

class Solution {
    List<List<Node>> graph;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        //최저 예상 택시요금을 계산해서 return
        //그래프 - 출발, 도착 지점, 가중치. 다익스트라
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<fares.length; i++){
            graph.get(fares[i][0]).add(new Node(fares[i][1], fares[i][2]));
            graph.get(fares[i][1]).add(new Node(fares[i][0], fares[i][2]));
        }
        
        //s, a, b에서 출발하는 모든 지점까지 최단거리
        //s->x + x->a + x->b 의 합이 최소가 되도록 
        int[] distS = dijkstra(s, n);
        int[] distA = dijkstra(a, n);
        int[] distB = dijkstra(b, n);
        
        int sum = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++){
            if(sum > distS[i]+distA[i]+distB[i]){
                sum = distS[i]+distA[i]+distB[i];
            }
        }
        
        answer = sum;
        
        return answer;
    }
    
    public int[] dijkstra(int s, int n){
        int[] dist = new int[n+1];
        for(int i=0; i<=n; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[s] = 0;
        pq.add(new Node(s, 0));
        
        while(!pq.isEmpty()){
            Node u = pq.poll();
            
            if(dist[u.n] < u.cost) continue;
            
            for(int i=0; i<graph.get(u.n).size(); i++){
                Node next = graph.get(u.n).get(i);
                if(dist[u.n] + next.cost < dist[next.n]){
                    dist[next.n] = dist[u.n] + next.cost;
                    pq.add(new Node(next.n, dist[next.n]));
                }
            }
        }
        
        return dist;
    }
    
    class Node implements Comparable<Node>{
        int n, cost;
        Node(int n, int cost){
            this.n = n;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o){
            //낮은 숫자 순으로 반환되게. 오름차순.
            return this.cost - o.cost;
        }
    }
}