[알고리즘 TIL] 합승 택시 요금

문제

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

프로그래머스

프로그래머스 lv3. 다익스트라

설명

다익스트라를 이용해 어피치와 무지가 택시를 타고 각자의 집에 도착하는 최소 요금을 구하는 문제이다. 지금까지는 단순히 그래프에서 시작 노드 s를 기준으로 다른 노드들까지의 최소 거리를 구하는 문제만 풀어봐서, 다른 사람의 풀이를 참고했다.

 

아이디어는 다음과 같다.

{ 요금 = 다익스트라(출발점,k) + 다익스트라(k,어피치의 도착지점) + 다익스트라(k,무지의 도착지점) } 에서 주어진 모든 지점을 하나씩 k에 대입하여 나온 요금들 중 최소를 반환하면 된다. 이때, k가 출발점과 동일한 경우, 둘이 합승하지 않고 각자의 집에 가는 경우이므로 위의 아이디어는 문제에서 요구한 모든 경우의 수를 탐색할 수 있게 된다.

맨 처음 제출한 코드에서 시간 초과가 났다. 이유는 모든 지점을 k에 하나씩 대입하는 반복문에서 다익스트라를 각각 3번씩 진행해서 그랬다. 생각해보니, 다익스트라는 시작점만 주어지면 나머지 모든 노드에 대한 최소 거리를 저장하므로, 시작점이 동일한 경우는 중복해서 다익스트라를 진행할 필요가 없다.

 

두 번째 제출한 코드는 다음과 같다. 시작점이 s인 경우는 모든 반복문에서 사용하므로 단 한번만 진행하고, 중간 지점 k에서 어피치, 무지 집으로 향하는 경우는 반복문마다 한 번 진행하여 결과물을 어피치와 무지에 각각 적용시켰다.

import java.util.*;

public class Q_합승택시요금_다익스트라 {

    static HashMap<Integer, ArrayList<int[]>> weightGraph;

    public static void main(String[] args) {
        Solution solution = new Solution();
        //지점 개수, 출발 지점, a의 도착 지점, b의 도착 지점
        int n = 6;
        int s = 4;
        int a = 6;
        int b = 2;
        //지점 사이 예상 택시 요금(양방향)
        int[][] fares = new int[][]{
                {4, 1, 10},
                {3, 5, 24},
                {5, 6, 2},
                {3, 1, 41},
                {5, 1, 24},
                {4, 6, 50},
                {2, 4, 66},
                {2, 3, 22},
                {1, 6, 25}
        };
        int answer = solution.solution(n, s, a, b, fares);
        System.out.println(answer);
    }

    static class Solution {
        public int solution(int n, int s, int a, int b, int[][] fares) {
            //다익스트라(s,k) + 다익스트라(k,a) + 다익스트라(k,b)
            //둘이 합승 안하는 경우는 다익스트라(s,k)=0이 되므로 모든 경우의 수가 포함됨!
            int answer = Integer.MAX_VALUE;
            //가중치 그래프에 시작 노드를 Key로, 종료 노드와 가중치 배열을 포함한 리스트를 Value로 저장
            weightGraph = new HashMap<>();
            for (int i = 0; i < fares.length; i++) {
                int startNode = fares[i][0];
                int endNode = fares[i][1];
                int weight = fares[i][2];
                addWeightData(startNode, endNode, weight);
                addWeightData(endNode, startNode, weight);
            }
            //시작지점이 s인 경우는 다익스트라를 한번만 하고 나온 결과물을 뒤에서 계속 이용(result1)
            int[] result1 = dijkstra(n, s);
            //중간 지점이 되는 k에 모든 지점을 대입
            for (int i = 1; i < n + 1; i++) {
                int distance = 0;
                if(s==i){
                    distance += (result1[a] + result1[b]);
                }
                else {
                    int[] result2 = dijkstra(n, i);
                    distance += (result1[i] + result2[a] + result2[b]);
                }
                if (distance < answer) {
                    answer = distance;
                }
            }

            return answer;
        }

        private int[] dijkstra(int n, int s) {
            int[] result = new int[n + 1];
            //최단 경로 배열 초기화
            Arrays.fill(result, Integer.MAX_VALUE);
            //우선순위 큐에 (다음노드, 누적거리) 저장
            //우선순위는 누적거리를 기준으로 하도록 설정
            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
            pq.add(new int[]{s, 0});
            //다익스트라 알고리즘
            while (!pq.isEmpty()) {
                int[] poll = pq.poll();
                int node = poll[0];
                int distance = poll[1];
                //노드 최단경로 갱신
                if (result[node] <= distance) continue;
                result[node] = distance;
                //인접 노드들 우선순위 큐에 저장
                if (!weightGraph.containsKey(node)) continue;
                for (int[] endNodeAndWeight : weightGraph.get(node)) {
                    //빙 둘러서 i에 도착하는 경로가 최단경로일 수 있으므로 마지막까지 반복
                    int adjNode = endNodeAndWeight[0];
                    int w = endNodeAndWeight[1];

                    int nextDistance = distance + w;
                    if (result[adjNode] > nextDistance) {
                        pq.add(new int[]{adjNode, nextDistance});
                    }
                }
            }
            return result;
        }

        private void addWeightData(int startNode, int endNode, int weight) {
            int[] endNodeAndWeight = new int[]{endNode, weight};
            if (weightGraph.containsKey(startNode)) {
                weightGraph.get(startNode).add(endNodeAndWeight);
                return;
            }
            ArrayList<int[]> value = new ArrayList<>();
            value.add(new int[]{endNode, weight});
            weightGraph.put(startNode, value);
        }
    }
}

하지만 이 또한 효율성에서 다 통과하지는 못했다.. 왤까? ㅜㅜ 이유는 나중에 알아봐야겠다.. (아시는 분 있으면 알려주세요..ㅠ)