[Programmers] 합승 택시 요금 - JAVA

문제 링크

문제 정의

• 무지와 어피치 두 명이 출발지에서 시작해서 각각의 도착지 A B로 가야함
• 두 명이 중간지점까지 택시를 합승하는 것이 비용이 저렴하다면 중간지점까지 같이 이동
• 그렇지 않다면 따로 택시 탑승

두 명이 출발지 s에서 각각의 도착지 A B까지 도착하는 최소 비용 구하기

---

접근 방법

이 문제는 간선이 주어지고 각각의 가중치가 다르기 떄문에 다익스트라로 접근해야 합니다.

이 문제의 핵심은 아래와 같습니다.

• 도착지가 기존의 다익스트라 문제와 달리 2개
• 비용에 따라 중간 지점이 생길 수도 있고 아닐 수도 있음

도착지가 2개이던 3개이던 출발지에서 다익스트라를 수행하면 얼마든지 구할 수 있습니다.
그러면 2번째 조건이 이 문제의 핵심이라는 것입니다.

불확실한 조건에 다익스트라를 수행하지 말자

이 문제의 함정인데 "그러면 중간 지점이 될 수 있는 모든 정점에서 다익스트라를 수행하고 s a b 까지의 비용이 최소가 되는 정점을 찾으면 되는거 아니야?" 라는 생각입니다.

그렇다면 노드의 수의 최대인 200이 노드의 수로 주어진다면?
다익스트라를 200번 수행해야 이 문제의 정답을 구할 수 있습니다.
TLE가 발생할 수도 있으며 발생하지 않더라도 노드의 수에 따라 증감하는 이 방식은
매우 비효율적이며 확장성이 부족한 접근 방법인 것을 알 수 있습니다.

그래서 위에서 말한 불확실한 조건에 다익스트라를 수행하는 것이 아닌
확실한 정보인 s a b에 다익스트라를 수행해야 합니다.

어디가 중간 지점이 될지 모르지만 s a b를 출발지점으로 다익스트라를 수행한다면
이 세 곳과 무조건 연결된 정점에 대한 비용을 구할 수 있게 됩니다.

즉, n이 무한히 커지더라도 다익스트라 3번으로 이 문제를 해결할 수 있게 됩니다.

핵심 로직

int answer = MAX;
int[] sDist = dijkstra(s);
int[] aDist = dijkstra(a);
int[] bDist = dijkstra(b);
        
for (int v = 1; v <= n; v++) {
	answer = Math.min(answer, sDist[v] + aDist[v] + bDist[v]);
}
        
return answer;

주어진 3개의 정점에 대한 다익스트라,
그리고 for문을 통한 모든 정점의 최소 비용 구하는 로직
이 간단한 코드로 해당 문제를 해결할 수 있습니다.

---

코드

import java.util.*;

class Edge implements Comparable<Edge>{
    int v;
    int w;
    
    public Edge (int v, int w) {
        this.v = v;
        this.w = w;
    }
    
    @Override
    public int compareTo(Edge o) {
        return this.w - o.w;
    }
}

class Node {
    int v;
    int w;
    Node node;
    
    public Node (int v, int w, Node node) {
        this.v = v;
        this.w = w;
        this.node = node;
    }
}

class Solution {
    static final int MAX = Integer.MAX_VALUE;
    static Node[] graph;
    static int sa;
    static int sb;
    static int N;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        N = n;
        graph = new Node[n+1];
        
        for (int[] fare : fares) {
            int u = fare[0];
            int v = fare[1];
            int w = fare[2];
            
            graph[u] = new Node(v, w, graph[u]);
            graph[v] = new Node(u, w, graph[v]);
        }
        
        int answer = MAX;
        int[] sDist = dijkstra(s);
        int[] aDist = dijkstra(a);
        int[] bDist = dijkstra(b);
        
        for (int v = 1; v <= n; v++) {
            answer = Math.min(answer, sDist[v] + aDist[v] + bDist[v]);
        }
        
        return answer;
    }
    
    
    static int[] dijkstra(int s) {
        int[] dist = new int[N+1];
        Arrays.fill(dist, MAX);
        dist[s] = 0;
        
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(s, 0));
        
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int v = edge.v;
            int w = edge.w;
            
            if (dist[v] < w) continue;
            
            for (Node node = graph[v]; node != null; node = node.node) {
                int nv = node.v;
                int nw = w + node.w;
                
                if (dist[nv] > nw) {
                    dist[nv] = nw;
                    pq.offer(new Edge(nv, nw));
                }
            }
        }
        
        return dist;
    }
}