문제링크

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

구현방법

• 처음 생각
• A와 B가 합승해서 가는경우
  • 어디까지 합승해서 가는지가 중요함.
• A와 B가 합승하지 않는 경우
  • 다익스트라로 최저값 계산을 해두면 가능

전체적인 최저값계산을 해두면 되지않을까? -> 다익스트라 알고리즘

문제의 관건

• 합승을 한경우가 더 값이 작은지 합승을 안하는게 더 작은지 체크 필요함.

힌트 - 플로이드 워셜 알고리즘을 사용한다. 음수 사이클만 아니면 음수의 가중치가 있어도 됨.

• 질문하기 와 검색을 했기 때문에 풀이를 보고 점수를 차감받고 진행
• 효율성 테스트에서는 다익스트라 더 좋은걸로 나옴
• 플로이드 워셜 알고리즘 과 다익스트라 알고리즘 2가지 경우가 존재

두 종류를 거의 풀어보지 못해서 코드를 보면서 진행함. -> 다익스트라와 플로이드 워셜 알고리즘은 학습이 좀더 필요해보임. (플로이드 워셜은 o(n^3)이 걸리기 때문에 조심해서 써야함.)

구현알고리즘

다익스트라 알고리즘 또는 플로이드-워샬 알고리즘

CODE

플로이드 -워셜 알고리즘

import java.util.*;

//플로이드-워셜 알고리즘
class Solution2{
    class Solution {
        public int solution(int n, int s, int a, int b, int[][] fares) {
            int[][] node = new int[n+1][n+1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    node[i][j] = 20000001;
                }
                node[i][i]= 0;
            }

            for(int idx = 0; idx < fares.length;idx++){
                node[fares[idx][0]][fares[idx][1]] = fares[idx][2];
                node[fares[idx][1]][fares[idx][0]] = fares[idx][2];
            }

            for(int k = 1; k<= n;k++){
                for(int i=1;i<=n;i++) {
                    for(int j =1; j<=n;j++) {
                        if(node[i][j] > node[i][k] + node[k][j]){
                            node[i][j] = node[i][k] + node[k][j];
                        }
                    }
                }
            }

            int min = Integer.MAX_VALUE;
            for(int idx =1; idx <=n;idx++){
                min =Math.min(min,node[s][idx] + node[idx][a] + node[idx][b]);
            }
            return min;


        }
    }

}

---

다익스트라 알고리즘

import java.util.*;
/**
 * 합승 택시 요금구하기
 * 다익스트랑 알고리즘
 * 플로이드 워셜 알고리즘도 가능함.
 *
 */
class Solution {

    static final int MAX = 20000001;
    static ArrayList<ArrayList<Edge>> graph;

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


        graph = new ArrayList<>();

        for(int idx=0;idx<= n;idx++){
            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,MAX);
        Arrays.fill(startB,MAX);
        Arrays.fill(start,MAX);

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

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

        return answer;
    }

    private 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;

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

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

    class Edge implements Comparable<Edge>{
        int index;
        int cost;
        Edge(int index, int cost){
            this.index = index;
            this.cost = cost;
        }

        public int compareTo(Edge e){
            return this.cost - e.cost;
        }
    }
}