문제 링크 ▶︎ 합승 택시 요금

합승 택시 요금

문제 파악

예전에 풀었던 ‘미로탈출’ 문제와 비슷한 방식으로 풀면 될 것 같다고 생각했다.
우선 어떤 지점까지 합승을 해야하는지는 완전탐색으로 찾아야 할 것 같다. 모든 경우를 조사한 다음 비용의 최소인 경우를 도출해야한다.

즉 시작 지점부터 특정 지점 k 까지의 비용과 k→a 비용과 k→b 비용의 합산의 최소를 찾아야한다.
두 지점간의 이동할때 최소비용을 구하는 다익스트라 알고리즘 함수 하나만 만들어서 세번 돌리면 될 것 같다.

접근 방법

1. 이웃한 지점 간의 이동할 때의 노드와 비용을 양방향으로 저장할 HashMap을 만들어주고 삽입한다.

2. 그리고 taxi 라는 두 지점간의 이동에서 최소비용을 리턴해주는 함수를 만드는데, 매개변수로는 n과 시작, 도착지점, 그리고 map을 준다.

3. 함수 내부에서는 비용을 기준으로 정렬한 우선순위큐를 만들고, 정수 배열로 만든 visit을 max로 채운다.

4. 그리고 출발지점의 visit은 0으로 바꾼 후, pq에 [start, 0] 시작지점과 비용 0을 삽입하고 while문을 순회한다.

5. 다음 이웃한 노드의 visit이 현재까지의 비용 + 다음 노드의 비용 보다 크다면 최솟값인 현재로 바꿔주고 pq에 삽입한다.

6. 도착지점에 도달하면 도착지점까지의 최소비용을 리턴한다. 다시 solution 에서 taxi를 모든 장소에 반복문을 돌면서 호출해주면 최종 최솟값이 나오게 된다.

코드 구현

import java.util.*;
class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        Map<Integer,List<int[]>> map = new HashMap<>();
        for(int i=1; i<=n; i++){
            map.put(i,new ArrayList<>());
        }
        for(int[] fare : fares){
            int aNode = fare[0], bNode = fare[1], cost = fare[2];
            map.get(aNode).add(new int[] {bNode, cost});
            map.get(bNode).add(new int[] {aNode, cost});
        }
        answer = taxi(n,s,a,map) + taxi(n,s,b,map);
        for(int i=1; i<=n; i++){
            if(i==s){
                continue;
            }
            int costI = taxi(n, s, i, map); 
            int costA = taxi(n, i, a, map); 
            int costB = taxi(n, i, b, map); 

            answer = Math.min(answer, costI + costA + costB);
        }

        return answer;
    }
    
    public int taxi(int n, int start, int end, Map<Integer,List<int[]>> map){
        Queue<int[]> pq = new PriorityQueue<>((a,b) -> a[1]-b[1]);
        int[] visit = new int[n+1];
        Arrays.fill(visit,Integer.MAX_VALUE);
        pq.add(new int[]{start,0});
        visit[start] = 0;
        while(!pq.isEmpty()){
            int[] out = pq.remove();
            int now = out[0], now_cost = out[1];
            if(now == end) {
                return now_cost;
            }
            for(int[] now_fare : map.get(now)){
                int next = now_fare[0], next_cost = now_fare[1] + now_cost;
                if(next_cost < visit[next]){
                    visit[next] = next_cost;
                    pq.add(new int[] {next, next_cost});
                }
            }
        }
        return Integer.MAX_VALUE;
    }
}

개선 사항

n이 많이 크지않아서 최종 비용을 찾는 과정은 완전탐색이라는 것을 알 수 있었고, 지점마다의 최소 비용은 따로 함수를 만들어서 풀게 돼서 더 깔끔하게 함수를 구현하는 방법을 배웠다.