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

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

프로그래머스

 

사용 알고리즘

• 최단 경로
• 다익스트라
• 플로이드 와샬

 

풀이

 

다익스트라

import java.util.*;
// 4번에서 출발해서 A와 B까지 도달하는 최단경로 노드를 찾는다.
// 
class Solution {
    static final int INF = Integer.MAX_VALUE / 2;
    static List<List<Node>> 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 [] fare : fares) {
            graph.get(fare[0]).add(new Node(fare[1], fare[2]));
            graph.get(fare[1]).add(new Node(fare[0], fare[2]));
        }
        
        int [] dist = dijkstra(s, n);
        int [] a_dist = dijkstra(a, n);
        int [] b_dist = dijkstra(b, n);
        
        for(int i = 1; i <= n; i++){
            if (dist[i] + a_dist[i] + b_dist[i] < 0) continue;
            answer = Math.min(answer, dist[i] + a_dist[i] + b_dist[i]);
        }
        
        return answer;
    }
    
    public int[] dijkstra(int start, int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>((p,q) -> p.cost - q.cost);
        int [] dist = new int[n+1];
        Arrays.fill(dist, INF);
        
        dist[start] = 0;
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            for(int i = 0; i < graph.get(cur.idx).size(); i++) {
                Node nxt = graph.get(cur.idx).get(i);
                if (dist[nxt.idx] <= cur.cost + nxt.cost) continue;
                dist[nxt.idx] = cur.cost + nxt.cost;
                pq.add(new Node(nxt.idx, dist[nxt.idx]));
            }
        }
        return dist;
    }
}

class Node { 
    int idx;
    int cost;
    public Node(int idx, int cost) {
        this.idx = idx;
        this.cost = cost;
    }
}

 

플로이드 와샬

import java.util.*;
class Solution {
    static final int INF = Integer.MAX_VALUE / 2;
    static int [][] d;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;
        
        d = new int[n+1][n+1];
        for(int i = 1; i <= n; i++) {
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }
        
        for(int i = 0; i < fares.length; i++){
            int u = fares[i][0];
            int v = fares[i][1];
            int c = fares[i][2];
            d[u][v] = c;
            d[v][u] = c;
        }
        
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        
        for(int i = 1; i <= n; i++) {
            if (d[s][i] + d[a][i] + d[b][i] < 0) continue;
            answer = Math.min(answer, d[s][i] + d[a][i] + d[b][i]);
        }
        
        
        return answer;
    }
}

 

 

회고

 

택시를 타는 지점인 S에서 출발하여, A와 B에 도달하는 최단경로를 구하는 문제다.

 

처음에 어떻게 S에서 출발해서 각각 최단경로를 갱신해 나갈 것인가? 

 

위 그림을 보면, S에서의 최단거리는 1번 노드이지만, A와 B의 거리까지 고려한다면 5번 노드가 전체 최단거리가 된다. 

 

그렇기 때문에, 각 노드에서 A,B,S까지의 거리의 합에 대한 최단거리를 구하면 된다.

 

다익스트라의 경우, S,A,B에서 각각 다익스트라 함수를 실행해서 최단경로를 구해보면

10 66 51 0 34 35 // S-> 각 노드까지 최단거리
25 48 26 35 2 0 // A -> 각 노드까지 최단거리
63 0 22 66 46 48 // B -> 각 노드까지 최단거리

 

이런식으로 최단경로가 갱신이 되고, 이 때 5번 노드가 (34 + 2 + 46) , 82로 최단경로가 된다.

 

플로이드 와샬 알고리즘의 경우에도 비슷한데, 플로이드 와샬은 인접 리스트가 아니라 인접 배열로 풀이를 진행을 하므로 이런식으로 최단경로가 저장될 것이다.

0 63 41 10 24 25
63 0 22 66 46 48
41 22 0 51 24 26
10 66 51 0 34 35
24 46 24 34 0 2
25 48 26 35 2 0

 

이 때는, S,A,B의 노드번호에 해당하는 값들을 계산하여 다익스트라와 마찬가지로 최단경로를 구해주면 된다.