Today I Learned

오늘은 다익스트라 알고리즘을 좀 더 높은 난이도로 풀어보려했다.

합승택시요금

문제

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

양방향 가중치 그래프 상에서 a, b, s점이 주어진다. a와 b에서 s까지 가야하는데 가는 동안 합석해서 비용을 한번만 치르는 것이 가능하다. 물론 합석을 하지 않을 경우가 비용이 더 저렴할 수도 있다. 각 간선의 요금 fares가 주어질 때 최소 비용을 return해라.

풀이 과정

1. 우선 음수가 아닌 가중치인 양방향 그래프에서 최소 가중치 경로를 구하는 문제이니 바로 다익스트라 알고리즘을 사용했다.

2. 그래프를 인접리스트로 구현하고, Node 클래스도 Comparable을 구현해서 생성해뒀다.

3. a,b,s 각각의 지점에서 출발했을때의 최소비용 배열을 다익스트라로 구한다.

4. startA[i] + startB[i] + startS[i]는 a,b,s점에서 i점까지의 비용을 더한 것이다. 즉, a,b가 각자 i점까지 온 뒤 i~s까지 합승해서 가는 경우라고 할 수 있다.

5. for문을 통해 위의 코드를 1~n까지 돌면서 가장 최소값이 되는 i지점, 합승지점을 찾아서 그때의 비용을 return하면 된다.

구현 코드

import java.util.*;
class Solution {
    static List<List<Node>> graph;
    
    class Node implements Comparable<Node> {
        int vertex;
        int weight;
        
        Node(int vertex, int weight){
            this.vertex = vertex;
            this.weight = weight;
        }
        
        @Override
        public int compareTo(Node other){
            return Integer.compare(this.weight, other.weight);
        }
        
    }
    
    public int[] dijkstra(int index, int[] cheapFares){
        Queue<Node> pq = new PriorityQueue<>();
        Arrays.fill(cheapFares, Integer.MAX_VALUE);
        cheapFares[index] = 0;
        Node startNode = new Node(index,0);
        pq.offer(startNode);
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int nv = node.vertex;
            int nw = node.weight;
            
            if(nw>cheapFares[nv]) continue;
            for(Node linkedNode : graph.get(nv)){
                int lv = linkedNode.vertex;
                int lw = linkedNode.weight;
                
                if(lw+nw < cheapFares[lv]){
                    cheapFares[lv] = lw+nw;
                    Node cheapNode = new Node(lv, cheapFares[lv]);
                    pq.offer(cheapNode);
                }
                
            }
            
        }
        return cheapFares;
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;
        
        // graph 초기화
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int[] fare : fares){
            int start = fare[0];
            int end = fare[1];
            int cost = fare[2];
            
            graph.get(start).add(new Node(end, cost));
            graph.get(end).add(new Node(start, cost));
        }
        
        int[] startA = new int[n+1];
        int[] startB = new int[n+1];
        int[] startS = new int[n+1];
        
        
        startA = dijkstra(a, startA);
        startB = dijkstra(b, startB);
        startS = dijkstra(s, startS);
        
        
        
        for(int i = 1; i <= n ; i ++) {
            answer = Math.min(answer, startA[i] + startB[i] + startS[i]);
        }
        return answer;
    }
}

기타

• 이번 문제는 간단하게 생각하면 간단하게 풀리는 문제이지만 초반에 너무 복잡하게 생각해서 헤맸다. HashMap으로 경로를 다 저장하면서 푸는 방식으로 접근했는데 구현이 까다로워 다른 방법을 생각했었다.

• 이 문제는 플로이드 워셜 알고리즘으로도 풀린다고 한다. 해당 내용에 대해서는 추후 정리해보려 한다.