[프로그래머스] 합승 택시 요금_다익스트라 알고리즘

문제 링크 :
https://school.programmers.co.kr/learn/courses/30/lessons/72413

코드를 알아보기 전에 먼저 문제와 알고리즘을 이해하여 스스로의 힘으로 코드를 짜보는 시간을 갖길 바랍니다.

용어 정리

포스팅을 시작하기 전에 아래와 같이 용어를 정리하겠습니다.

• vertex(지점) : 그래프의 각 꼭짓점.
• edge(선단) : 그래프의 지점 사이를 잇는 선.
• cost(비용) : 선단 너머의 지점까지 이동하는 데에 필요한 비용.
• adjacent vertex(인접한 지점) : 어떤 지점과 선단으로 이어져 있는 지점.

해당 포스트에서는 영문 용어를 사용하겠습니다. (영문 용어에 익숙해지는 게 좋으니까요^^)

문제 이해하기

해당 문제는 도착 지점이 두 개라는 변형이 있지만, 기본적으로 최단거리 구하기 문제입니다.

최단거리 알고리즘으로는 다익스트라 알고리즘, 벨만포드 알고리즘이 대표적입니다.

음수의 값이 edge의 cost로 주어졌을 때 계산이 불가능한 다익스트라 알고리즘의 한계를 극복하기 위해 벨만포드 알고리즘이 고안되었습니다.

요금 f는 1 이상 100,000 이하인 자연수입니다.

해당 문제는 위와 같은 제한 사항이 있으므로 다익스트라 알고리즘으로 구현해보기로 하겠습니다.

다익스트라 알고리즘 이해하기

다익스트라 알고리즘의 구조는 아래와 같습니다.

1. 시작 vertex를 기준으로 각 vertex의 최단 거리를 저장할 최단 거리 배열을 생성한다.
2. 현재 vertex로 시작 vertex를 지정한다.
3. 현재 vertex의 adjacent vertex 중 방문한 적 없는 모든 vertex와 연결된 edge의 cost를 최단 거리 배열에 저장한다.
4. 최단 거리 배열에 있는 vertex 중 가장 cost가 작은 vertex를 현재 vertex로 선택한다.
5. 현재 vertex의 adjacent vertex 중 방문한 적 없는 vertex를 다음 vertex로 선택한다.
6. 다음 vertex와 연결된 edge의 cost와 최단 거리 배열에 저장된 현재 vertex의 값을 더한 값이 다음 vertex의 최단 거리 배열에 저장된 값보다 작다면 최단 거리 배열에 저장된 다음 vertex의 값을 전자의 값으로 갱신한다.
7. 현재 vertex의 모든 adjacent vertex를 방문할 때까지 5-6번의 과정을 반복한다.
8. 모든 vertex를 방문할 때까지 4-7번의 과정을 반복한다.

간단해 보이는데 이해는 쉽지가 않습니다. 문제에서 제시된 예제를 보며 이해해봅시다.

S부터 모든 vertex까지의 최단거리를 다익스트라 알고리즘으로 구하고자 한다면 처음엔 아래같은 최단 거리 배열이 만들어질 겁니다. (index 0은 vertex의 indexing이 1부터 시작함에 따라 사용하지 않을 겁니다.)

0	1	2	3	4	5	6
∞	∞	∞	∞	∞	∞	∞

s인 4번 vertex를 현재 vertex로 삼고 adjacent vertex의 cost를 최단 거리 배열에 기록하면 아래와 같이 갱신되겠죠. (4번에서 4번으로 가는 cost는 0으로 지정합니다.)

0	1	2	3	4	5	6
∞	10	66	∞	0	∞	50

이제 4번은 방문을 했으니 4번을 제외한 vertex 중에 가장 작은 값인 10을 가지는 vertex는 1번이겠죠?

1번을 현재 vertex로 삼고 adjacent vertex를 살펴보면 3번과 5번, 6번이 있습니다. 3번을 다음 vertex로 본다면 무한대보다 10 + 41 = 51이 더 작으니 3번의 값을 갱신할 수 있겠죠?

5번과 6번도 이와 같이 처리하면 최단 거리 배열은 이렇게 갱신될 것입니다.

0	1	2	3	4	5	6
∞	10	66	51	0	34	35

그럼 이제 1번도 방문한 것이 됩니다. 다음으로 현재 vertex로 지정될 vertex는 6번이 되겠죠?

이런 식으로 모든 vertex를 방문할 때까지 진행하다보면 S를 기준으로 모든 vertex의 최단 거리를 구할 수 있습니다!

2개의 도착 지점을 가지는 최단 거리 알고리즘 이해하기

앞서 다익스트라 알고리즘을 이해해보았는데요. 그렇담 두 개의 도착 지점이 있다고 할 때 합승까지 한다면 어떻게 최단 거리를 구할 수 있을까요? 아래의 과정으로 사고해보시면 쉽게 풀릴 것입니다.

1. 출발 vertex와 모든 vertex 간의 최단 거리를 구한다.
2. 첫 번째 도착 vertex와 모든 vertex 간의 최단 거리를 구한다.
3. 두 번째 도착 vertex와 모든 vertex 간의 최단 거리를 구한다.
4. 출발 vertex와 환승 vertex 간의 최단 거리를 두 사용자가 합승한다고 가정할 때 해당 최단 거리와 각 도착 vertex와 환승 vertex 간의 최단 거리를 모두 더해 환승 vertex까지 합승할 때의 요금을 계산한다.
5. 4번의 값 중 가장 적은 요금을 구한다.

조금 이해가 어려운가요? 다시 예제를 보며 이해해봅시다.

1번 vertex가 환승 vertex라고 생각해봅시다. 출발 vertex과의 최단 거리는 10입니다. A와 B vertex의 최단 거리는 각각 25와 63입니다. 출발 vertex부터 환승 vertex까지 두 사용자가 합승했다면 요금은 10입니다. 그 후 환승하여 각 도착 vertex까지 갔다고 한다면 총요금은 98이 될 겁니다.

그렇다면 5번 vertex가 환승 vertex라고 생각해볼까요? 출발 vertex과의 최단 거리는 34입니다. A와 B vertex의 최단 거리는 각각 46과 2입니다. 출발 vertex부터 환승 vertex까지 두 사용자가 합승했다면 요금은 34입니다. 그 후 환승하여 각 도착 vertex까지 갔다고 한다면 총요금은 82가 될 겁니다.

1번에서 환승할 때보다 5번에서 환승할 때가 더 요금이 저렴하지요?

tip

• fares에는 출발 지점과 도착 지점이 한 번씩만 기재되어 있습니다. 그래프를 생성할 때 각 vertex마다 모든 adjacent vertex를 연결할 수 있도록 고려해보세요.
• 다익스트라 알고리즘은 기본적인 자료구조를 사용했을 때 O(V^2)의 복잡도를 가집니다. 하지만 Heap으로 구현했을 때 복잡도는 O((V+E)log V)로 낮아집니다.

문제 해결 코드(Java)

import java.util.*;

class Solution {
    static class Vertex{
        int idx, cost;
        
        public Vertex(int i, int c){
            this.idx = i;
            this.cost = c;
        }
    }
    
    public int[] Dijkstra(ArrayList<ArrayList<Vertex>> g, int v, int start){
        int[] min_d = new int[v + 1]; // 최소 거리를 저장.
        
        //가장 큰 값으로 최단 거리를 초기화.
        for(int i = 0; i < min_d.length; i++){
            min_d[i] = Integer.MAX_VALUE;
        }
        
        //현재 vertex의 인접 vertex를 저장할 heap 생성.(cost를 기준으로 가장 오름차순.)
        PriorityQueue<Vertex> Heap = new PriorityQueue<Vertex>(
            (o1, o2) -> Integer.compare(o1.cost, o2.cost));
        
        Heap.offer(new Vertex(start, 0)); //가장 먼저 시작할 vertax는 start.
        min_d[start] = 0; //start에서 start로 가는 최단 거리는 0.
        
        System.out.println(start + "번 vertex의 최단 거리 변천사 : ");
        
        while(!Heap.isEmpty()){
            Vertex curr_v = Heap.poll(); //가장 작은 cost를 가진 vertex를 가져옴.
            
            //이미 최단 거리를 구한 경우 넘어감.
            if(min_d[curr_v.idx] < curr_v.cost) continue;
            
            //현재 vertex의 인접 vertex의 수만큼 반복.
            for(int i = 0; i < g.get(curr_v.idx).size(); i++){
                //현재 vertex의 인접 vertex를 순차적으로 가져옴.
                Vertex adj_v = g.get(curr_v.idx).get(i);
                
                //현재 vertex의 cost와 인접 vertex의 cost를 더한 값이 
                //기존 최단 거리보다 짧으면 갱신.
                if(min_d[adj_v.idx] > adj_v.cost + curr_v.cost){
                    min_d[adj_v.idx] = adj_v.cost + curr_v.cost;
                    Heap.offer(new Vertex(adj_v.idx, min_d[adj_v.idx]));
                    System.out.println(Arrays.toString(min_d));
                }
            }
        }
        
        System.out.println();
        
        return min_d;
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;
        
        //그래프 생성
        ArrayList<ArrayList<Vertex>> graph = new ArrayList<ArrayList<Vertex>>();
        for(int i = 0; i < n + 1; i++){
            graph.add(new ArrayList<Vertex>());
        }
        for(int i = 0; i < fares.length; i++){
            graph.get(fares[i][0]).add(new Vertex(fares[i][1], fares[i][2]));
            graph.get(fares[i][1]).add(new Vertex(fares[i][0], fares[i][2]));
            //c, d를 반전한 edge도 각 vertex에 연결.
        }
        
        //각 지점의 최단 거리를 구함.
        int[] s_min = Dijkstra(graph, n, s);
        int[] a_min = Dijkstra(graph, n, a);
        int[] b_min = Dijkstra(graph, n, b);
        
        //가장 적은 요금을 구함.
        for(int i = 1; i < n + 1; i++){
            if(answer > s_min[i] + a_min[i] + b_min[i])
                answer = s_min[i] + a_min[i] + b_min[i];
        }
        
        return answer;
    }
}

출력 내용

예제로 주어진 값으로 출력했을 때 아래의 결과를 볼 수 있습니다.
최단 거리의 상태를 확인하기 위해 구현한 것이므로 해당 출력 내용을 굳이 구현할 필요는 없습니다.

4번 vertex의 최단 거리 변천사 : 
[2147483647, 10, 2147483647, 2147483647, 0, 2147483647, 2147483647]
[2147483647, 10, 2147483647, 2147483647, 0, 2147483647, 50]
[2147483647, 10, 66, 2147483647, 0, 2147483647, 50]
[2147483647, 10, 66, 51, 0, 2147483647, 50]
[2147483647, 10, 66, 51, 0, 34, 50]
[2147483647, 10, 66, 51, 0, 34, 35]

6번 vertex의 최단 거리 변천사 : 
[2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2, 0]
[2147483647, 2147483647, 2147483647, 2147483647, 50, 2, 0]
[2147483647, 25, 2147483647, 2147483647, 50, 2, 0]
[2147483647, 25, 2147483647, 26, 50, 2, 0]
[2147483647, 25, 2147483647, 26, 35, 2, 0]
[2147483647, 25, 48, 26, 35, 2, 0]

2번 vertex의 최단 거리 변천사 : 
[2147483647, 2147483647, 0, 2147483647, 66, 2147483647, 2147483647]
[2147483647, 2147483647, 0, 22, 66, 2147483647, 2147483647]
[2147483647, 2147483647, 0, 22, 66, 46, 2147483647]
[2147483647, 63, 0, 22, 66, 46, 2147483647]
[2147483647, 63, 0, 22, 66, 46, 48]