합승 택시 요금 - JAVA

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

프로그래머스

---

이 문제는 최단 거리를 찾는 문제이므로 다익스트라 알고리즘을 사용하면 된다!

근데 문제는? 내가 다익스트라 알고리즘을 모른다는거~~

그래서 공부함 ㅎ_ㅎ

 

https://yummy0102.tistory.com/433

[알고리즘] 다익스트라 알고리즘

 

 

아무튼 다익스트라 알고리즘을 통해서 구현하면 되는데, 우선 S, A, B에서부터 모든 노드까지의 최단 거리를 다 구한다

그리고 각 노드별로 s, a, b까지의 최단 거리의 합이 최솟값인 곳을 찾으면 된다!

그니까 다익스트라를 s, a, b마다 한 번씩 총 3번을 호출하면 된다

 

나는 우선순위 큐를 사용해서 다익스트라를 구현하는게 훨씬 시간 효율성이 좋다고 해서 그렇게 구현했다!

 

 

자바 코드)

import java.util.*;

class Edge implements Comparable<Edge> {
    int index;
    int cost;

    Edge(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return 0;
    }
}

class Solution {
    static final int INF = 200 * 100000 + 1;
    static List<List<Edge>> graph = new ArrayList<>();

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

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

        int[] startA = new int[n + 1];
        int[] startB = new int[n + 1];
        int[] start = new int[n + 1];

        Arrays.fill(startA, INF);
        Arrays.fill(startB, INF);
        Arrays.fill(start, INF);

        startA = dijkstra(a, startA);
        startB = dijkstra(b, startB);
        start = dijkstra(s, start);

        for(int i=1;i<=n;i++) {
            answer = Math.min(answer, startA[i]+startB[i]+start[i]);
        }
        return answer;
    }

    public int[] dijkstra(int start, int[] costs) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0));
        costs[start] = 0;

        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int nIndex = now.index;
            int nCost = now.cost;

            if (nCost > costs[nIndex]) {
                continue;
            }

            List<Edge> edges = graph.get(nIndex);
            for (Edge e : edges) {
                int cost = e.cost + costs[nIndex];

                if (cost < costs[e.index]) {
                    costs[e.index] = cost;
                    pq.offer(new Edge(e.index, cost));
                }
            }
        }
        return costs;
    }
}

마지막에 제출하기 전에 헷갈렸던 건 문제에서 인덱스를 1부터 사용하기 때문에 n까지 =으로 처리해서 n+1 길이로 만들어서 사용해야 했다

근데 그걸 깜빡하고 반복문을 n 직전까지만 해서 좀 삐끗했당ㅎㅎㅎ

아무튼 다익스트라 제대로 써본건 이 문제가 처음인것 같아서 좋다!

 

 

 

 

 

 

---

참고)

https://wellbell.tistory.com/m/101