[프로그래머스/Level3] 합승 택시 요금 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 다익스트라

필요 자료구조
- (도착지, 거리) 정보 저장용 인접 리스트
- a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열
- 다익스트라용 우선순위 큐

 

. a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열을 최댓값 (200 * 10만 +1)으로 설정한다.

. a,b,s에서 시작해서 각 점들까지의 최단 거리를 구하는 다익스트라를 총 3번 실행한다.

  - 현재 번호와 연결된 점들을 지나면서, 현재 연결된 점과 다음 연결된 점까지의 거리를 더한 값이 다음 연결된 점까지의 거리보다 짧다면, 다음 연결된 점의 거리를 더 짧은 값으로 갱신한다. → if(dist[next.idx] > dist[now.idx] + next.val)

 

. 경유지 1부터 n번 점까지 돌며, a~i까지의 거리 + b~i까지의 거리 + s부터 i까지의 거리를 더했을 때 가장 작은 값을 정답으로 출력한다.

 

 

💥 유의사항

최단 거리를 구하고, 경유하는 경우까지 계산해야 한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int MAX = 200 * 100_000 + 1;
    static ArrayList<ArrayList<Node>> graph;
    static int answer = Integer.MAX_VALUE;
        
    public int solution(int n, int s, int a, int b, int[][] fares) {                
        graph = new ArrayList<>();
        for(int i = 0 ; i <= n ; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 양방향
        for(int[] f : fares) {
            graph.get(f[0]).add(new Node(f[1], f[2]));
            graph.get(f[1]).add(new Node(f[0], f[2]));
        }       
        
        int[] startA = new int[n+1];    // a에서 시작해서 각 점들까지의 최단 거리 구하기
        int[] startB = new int[n+1];    // b에서 시작해서 각 점들까지의 최단 거리 구하기
        int[] start  = new int[n+1];    // s에서 시작해서 각 점들까지의 최단 거리 구하기
        
        Arrays.fill(startA, MAX);
        Arrays.fill(startB, MAX);
        Arrays.fill(start,  MAX);
        
        startA = dijkstra(a, startA);
        startB = dijkstra(b, startB);
        start  = dijkstra(s, start);
        
        for(int i = 1 ; i <= n ; i++) {
            answer = Math.min(answer, startA[i] + startB[i] + start[i]);
        }
                
        return answer;
    }
    
    private static int[] dijkstra(int start, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0)); // 시작점
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
                        
            if(now.val > dist[now.idx])    continue;
            
            ArrayList<Node> nodes = graph.get(now.idx);
            for(Node next : nodes) {                
                if(dist[next.idx] > dist[now.idx] + next.val) {   // 더 작은 거리로 갱신
                    dist[next.idx] = dist[now.idx] + next.val;
                    pq.offer(new Node(next.idx, now.val));
                }
            }
        }
        
        return arr;
    }
}
 
class Node implements Comparable<Node> {
    int idx, val;
    
    public Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
    
    // 거리 기준 오름차순 정렬
    @Override
    public int compareTo(Node n) {
        return this.val -  n.val;
    }
}

 

 

➕ 다른 풀이 방식

- 플로이드 워셜 

import java.util.*;
 
class Solution {
    static int MAX = 200 * 100_000 + 1;
    static int[][] dp;
        
    public int solution(int n, int s, int a, int b, int[][] fares) {                
        dp = new int[n+1][n+1];
        for(int i = 0 ; i <= n ; i++) {
            Arrays.fill(dp[i], MAX);
            dp[i][i] = 0;
        }
        
        // 양방향
        for(int[] f : fares) {
            dp[f[0]][f[1]] = f[2];
            dp[f[1]][f[0]] = f[2];
        }       
        
        for(int k = 1 ; k <= n ; k++) {
            for(int i = 1 ; i <= n ; i++) {
                for(int j = 1 ; j <= n ; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        
        int answer = dp[s][a] + dp[s][b];
        
        // 경유 지점을 거치는 경우
        for(int i = 1 ; i <= n ; i++) {
            answer = Math.min(answer, dp[s][i] + dp[i][a] + dp[i][b]);
        }
                
        return answer;
    }
}

---

💦 어려웠던 점

- 다익스트라도 생각하고, 플로이드 워셜도 생각하긴 했는데 경유지를 거치는 경우도 고려해 줘야 하는 걸 놓쳤다.

 

 

🧐 새로 알게 된 내용

- a에서 각 점, b에서 각 점, s에서 각 점까지 경유하면서 최단 거리를 모두 구해봐야 하는 것

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스 - 합승 택시 요금 문제 (자바)