[프로그래머스] 72413 합승 택시 요금 - JAVA - Lv.3

[프로그래머스] 72413 합승 택시 요금 - JAVA - Lv.3

문제

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

프로그래머스

문제 분석

풀이방법

• 문제는 S에서 두 사람이 택시 합승을 하여 특정 지점(I)까지 같이 이동 후 각자 A, B로 이동할 때 최소 비용을 구하는 문제이다.
• 예시에서 살펴볼 때 최소값은 4>1>5까지 합승을 하고 그 뒤로 5>6, 5>3>2 경로로 A와 B 지점으로 가는 방법이 최소이다.
• 합승하여 갈라지는 지점을 I라 했을 때 최솟값은 S-I, I-A, I-B의 최솟값을 구하면 된다. 다익스트라 방식을 이용하였다.

+

• 제일 처음은 다익스트라로 S-I, I-A, I-B를 각각 구했는데 효율성 테스트 탈락
• I-S, I-A, I-B를 구하기 위해 `for( i = 1; i < n; i++){}`로 계산했는데 이것도 효율성 테스트 탈락. 지점이 매우 많을 경우 계산이 많아진다.
• S, A, B 기준으로 모든 지점까지 거리를 계산해 문제를 풀면 된다.

코드

import java.util.*;

class Solution {

    static List<int[]>[] graph;
    static int N;
    static int INF = (int) 10e9;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        N = n;
        graph = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] fare : fares) {
            graph[fare[0]].add(new int[]{fare[1], fare[2]});
            graph[fare[1]].add(new int[]{fare[0], fare[2]});
        }

        int answer = INF;

        int[] sDist = dijkstra(s);
        int[] aDist = dijkstra(a);
        int[] bDist = dijkstra(b);
        for (int i = 1; i <= n; i++) {
            if (sDist[i] == INF || aDist[i] == INF || bDist[i] == INF) {
                continue;
            }
            answer = Math.min(answer, sDist[i] + aDist[i] + bDist[i]);
        }
        return answer;
    }

    static public int[] dijkstra(int from) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[from] = 0;
        pq.add(new Node(0, from));
        while (!pq.isEmpty()) {
            Node now = pq.poll();

            if (dist[now.getNow()] != 0 && dist[now.getNow()] != INF) {
                continue;
            }
            dist[now.getNow()] = now.getDist();

            for (int[] nextNode : graph[now.getNow()]) {
                if (dist[nextNode[0]] == INF) {
                    pq.add(new Node(now.getDist() + nextNode[1], nextNode[0]));
                }
            }
        }
        return dist;
    }
}

class Node implements Comparable<Node> {
    private int dist;
    private int now;

    public Node(int dist, int to) {
        this.dist = dist;
        this.now = to;
    }

    public int getDist() {
        return this.dist;
    }

    public int getNow() {
        return this.now;
    }

    @Override
    public int compareTo(Node node) {
        return this.dist - node.getDist();
    }
}

결과