[프로그래머스 Lv3][자바] 합승 택시 요금

❓문제설명

합승 택시 요금

프로그래머스

---

🔍문제해석

어떤걸 풀어야 할까?

• 각 지점과 그 지점을 오가는 간선에 택시 요금이 주어진다.
• 무지와 어피치는 택시 비용을 줄이기 위해 합승을 하기로한다. 
• 그렇게 합승을 했을때 발생하는 택시비용 중 가장 최소금액을 구해라. 
• 만약 합승 하는 것보다 각자의 도착지점을 향하는게 더 적은 요금이 든다면, 그 값을 리턴해라.

---

🧐문제풀이

• 문제 풀이 구상

각 지점과 간선의 비용이 주어진 것을 보아 인접리스트를 생각하였다.

근데 그 인접리스트를 이용해 어떻게 최소 금액을 구해야할지는 생각하지 못하고, 참고할 만한 블로그를 찾았다.

https://velog.io/@pppp0722/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level3-%ED%95%A9%EC%8A%B9-%ED%83%9D%EC%8B%9C-%EC%9A%94%EA%B8%88-Java

 

1. 출발점에서 각 지점으로 향하는 최소택시비를 다익스트라 알고리즘을 통해 구한다. 이것은 무지와 어피치가 출발지점으로 부터 각 지점까지 합승한 요금이 될 것이다. 

2. for문을 돌면서 출발지점 i로 부터 각 지점으로 향하는 최소 택시비를 담은 배열을 구한다. 이것은 합승 이후, i의 출발지로 부터 어피치와 무지 각자의 집까지 가는 최소 요금일 것이다. 

3. 결론은 i까지 환승한 최소택시비 + i지점으로 부터 무지 집까지 최소 택시비 + i지점으로 부터 어피치 집까지 최소택시비를 구하고, 그 중 가장 적은 비용을 리턴하면 된다.

 

• 알고리즘 선택

서로 연결된 지점을 보고 인접리스트 적용

최소 비용을 구하기 위한 우선순위 큐 적용

간선에 가중치가 있고 그 가중치가 양수이기 때문에 다익스트라 알고리즘 적용

 

---

！제출코드

1. 각 간선별 요금을 저장하기 위한 인접리스트 생성(양방향)
2. 주어진 출발 지점으로 부터 각 지점까지의 최소 택시비를 저장한 배열 구하기
3. 각 지점을 돌면서 i지점을 출발하여 부터 각 지점까지의 택시비를 저장한 배열을 구한다.
4. i지점까지 합승을 한 비용과 i 지점으로 부터 무지 집까지의 택시비용, i 지점으로 부터 어피치 집까지의 택시비용을 더한다.
5. 현재의 최소금액과 비교해서 더 작은 값을 answer에 담는다. 
6.  다익스트라 알고리즘
7. 최소비용을 담을 배열, 지점을 두번 방문하지않도록 방문 여부를 체크할 배열,각 지점의 이동 노드와 요금을 담을 queue
8. 최소값 비교를 위해 초기값을 max로 설정한다.
9. 출발점의 최소비용은 없기 때문에 0으로 설정, 그 하위 간선을 찾기 위해 queue에 담고 while문을 시작한다.
10. 방문한 적이 있다면 다음 노드로 넘기기
11. 현재 지점의 간선정보를 가져와서 이동한 지점이 갖고 있는 최소요금보다 현재 요금 + 이동한 지점까지의 요금이 이 더 적을때만 이동을 하고 (현재 요금 + 이동한 지점까지의 요금)을 최소요금을 담는 배열에 대입한다.
12. 이동노드와 요금을 담는 클래스 
13. 우선순위 큐 사용을 위해 Comparable을 구현받고, 금액 오름차순으로 정렬을 지정해주었다,

 

import java.util.*;

class Solution {

    static int routeLength;
    static int start;
    static ArrayList<ArrayList<Fare>> list = new ArrayList<>();
    
   public static int solution(int n, int s, int a, int b, int[][] fares) {

        routeLength = n;
        start = s;
        
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        // (1)
        for (int i = 0; i < fares.length; i++) {
        
            int [] route = fares[i];
            Fare fare = new Fare(route[1], route[2]);
            list.get(route[0]).add(fare);
            Fare fare2 = new Fare(route[0], route[2]);
            list.get(route[1]).add(fare2);
        }
        
        int answer = Integer.MAX_VALUE;
        // (2)
        int [] together = dijkstra(start);
        // (3)
        for(int i =1; i<=routeLength; i++){
            int [] alone = dijkstra(i);
            // (4) 같이 타고온 금액 + 각자 택시탄 금액 ;
            int fare = together[i] + alone[a] + alone[b];
            // (5)
            answer = Math.min(answer, fare);
        }

        return answer;
    }
    // (6)
    static int[] dijkstra(int start){
    	// (7)
        int [] minFare = new int[routeLength+1];
        boolean[] visited = new boolean[routeLength+1];
        PriorityQueue<Fare> pq = new PriorityQueue<>();
        // (8)
        Arrays.fill(minFare, Integer.MAX_VALUE);
        
        // (9)시작
        minFare[start] = 0;
        pq.add(new Fare(start, 0));
        
        while(!pq.isEmpty()){
        
            Fare currentFare = pq.poll();
            // (10)
            if(visited[currentFare.arrival]) continue;

            visited[currentFare.arrival] = true;
            for(Fare fare : list.get(currentFare.arrival)){
                // (11)현재 해당 정점으로 향한 택시비보다 더 적을때만
                if(minFare[fare.arrival] > fare.fare + currentFare.fare){
                    minFare[fare.arrival] = fare.fare + currentFare.fare;
                    pq.add(new Fare(fare.arrival, fare.fare + currentFare.fare));
                }
            }
        }


       return minFare;
    }
    // (12)
    public static class Fare implements Comparable<Fare>{
        int arrival;
        int fare;

        public Fare(int arrival, int fare) {
            this.arrival = arrival;
            this.fare = fare;
        }
      
        // (13)
        @Override
        public int compareTo(Fare o) {
            return this.fare - o.fare;
        }
    }
}