📃 문제

프로그래머스 - 합승 택시 요금

📝 풀이

이 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제다.

문제를 푸는 핵심은 먼저 각 지점(A, B, S)에서 출발해 전체 노드를 최단 경로로 방문시켜서 3개의 방문 그래프를 만든다.
각 방문 그래프에서 노드까지의 합을 다 더해주면 S에서 출발해서 A, B로 가는 경로의 요금이 된다.

Ex)
S에서 출발하여 1번 노드까지 합승하고 각각의 도착 지점으로 가는 경로의 요금은

• A -> 1번까지 가는 경로의 요금 : 25
• B -> 1번까지 가는 경로의 요금 : 22 + 41 = 63
• S -> 1번까지 가는 경로의 요금 : 10
• 총합 : 98

이를 활용해서 세 지점에서 전체 노드 방문을 시킨 후
각 노드까지의 총합을 비교하여 최소가 되는 값을 찾으면 된다.

Java 코드

import java.util.*;

class Node implements Comparable<Node> {
    int idx, cost;
    
    Node(int idx, int cost) {
        this.idx = idx;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node o1) {
        return Integer.compare(this.cost, o1.cost);
    }
}

class Solution {
    
    static List<Node>[] graph;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;
        
        graph = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<Node>();
        }
        
        for (int[] fare : fares) {
            graph[fare[0]].add(new Node(fare[1], fare[2]));
            graph[fare[1]].add(new Node(fare[0], fare[2]));
        }
        
        int[] distA = new int[n+1];   // A의 방문 그래프
        int[] distB = new int[n+1];   // B의 방문 그래프
        int[] dist = new int[n+1];   // S의 방문 그래프
        
        Arrays.fill(distA, Integer.MAX_VALUE);
        Arrays.fill(distB, Integer.MAX_VALUE);
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        distA = dijkstra(a, distA);
        distB = dijkstra(b, distB);
        dist = dijkstra(s, dist);
        
        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, distA[i] + distB[i] + dist[i]);
        }
        
        return answer;
    }
    
    static int[] dijkstra(int start, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        dist[start] = 0;
        
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (dist[now.idx] < now.cost)   continue;
            
            for (Node next : graph[now.idx]) {
                if (dist[next.idx] > now.cost + next.cost) {
                    dist[next.idx] = now.cost + next.cost;
                    pq.offer(new Node(next.idx, dist[next.idx]));
                }
            }
        }
        return dist;
    }
}