(JAVA) 합승 택시 요금

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

풀이

최소거리비용 알고리즘으로 유명한 다익스트라 알고리즘을 사용한 풀이이다. 전체적인 문제 해결 방법은 아래와 같다.

1. mat이라는 이름의 인접 행렬을 각 지점 간의 금액을 담고 있는 fares 배열을 사용하여 생성한다.
2. mat을 바탕으로 두 사람이 합승하여 출발 지점부터 다른 모든 정점까지 가는 최소 비용을 다익스트라 알고리즘을 사용하여 알아내고 이를 both라는 배열에 저장한다.
3. 시작 정점 뿐만 아니라 다른 정점들도 순회하며, 다익스트라 알고리즘을 사용하여 모든 정점까지의 최소 비용을 알아내고 이를 alone이라는 배열에 저장한다.
4. 최종적으로 위에서 알아낸 both, alone을 사용하여 (시작정점에서 특정 지점까지의 거리) + (한 사람의 특정 지점에서 목적지까지의 거리) + (다른 사람의 특정 지점에서 목적지까지의 거리)의 최소값을 알아내면 이 값이 알아내고자 하는 정답이 된다. 

import java.util.*;

class Solution {
    int[][] mat;
    int total;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        mat = new int[n][n]; // 간선 간의 거리 정보를 담을 인접행렬
        total = n;
        
        // 인접행렬에 거리 정보 저장
        for (int i = 0; i < fares.length; i++){
            int u = fares[i][0] - 1;
            int v = fares[i][1] - 1;
            int fare = fares[i][2];
            mat[u][v] = fare;
            mat[v][u] = fare;
        }
        
        int[] both = dijkstra(s-1); // 시작 정점에서 모든 다른 정점에 대한 거리를 다익스트라 알고리즘을 사용하여 계산
        int minCost = Integer.MAX_VALUE;
        for(int i = 0; i < total; i++) { 시작 정점 외의 다른 정점에서도 다익스트라 알고리즘을 통해 거리 계산
            int[] alone = dijkstra(i);
            int cost = both[i] + alone[a - 1] + alone[b - 1]; // 총 택시 요금 = 합승해서 가는 비용 + 어피치가 목적지까지 혼자 탄 비용 + 무지 혼자 탄 비용
            if(cost < minCost) {
                minCost = cost; // 현재 가격이 최소 가격보다 더 싸다면 최소 요금 저장
            }
        }

        return minCost;
    }
    
    // 다익스라 알고리즘
    int[] dijkstra(int start){
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a->a[0])); // 우선순위 큐를 사용해 최소 거리를 가진 노드를 선택
        boolean[] visited = new boolean[total]; // 각 노드의 방문 여부
        int[] distanceList = new int[total]; // 다른 노드까지의 최단 거리를 담을 배열
        Arrays.fill(distanceList, Integer.MAX_VALUE);
        distanceList[start] = 0; // 시작 노드의 최단거리는 0
        q.add(new int[] {0, start}); // 시작 노드와 시작 노드까지의 최단거리(0)을 배열에 저장 
		
        // 우선 순위 큐가 빌 때까지 순회
        while(!q.isEmpty()) {
            int[] current = q.remove(); // 거리를 계산할 현재 노드를 꺼냄
            int u = current[1]; // 현재 노드의 인덱스
            if (visited[u]) continue; // 현재 노드를 이미 방문했다면 다음 노드를 처리

            visited[u] = true; // 방문 처리
            for (int v = 0; v < total; v++) { // 모든 다른 노드를 순회하면서 처리
                if(mat[u][v] == 0) continue; // 거리가 없다면 건너뛰기

                if(distanceList[u] + mat[u][v] < distanceList[v]) { // 새로운 간선의 거리에 현재까지의 거리를 더한 값이 기존의 최소 거리보다 작다면
                    distanceList[v] = distanceList[u] + mat[u][v]; // 새로운 최소 거리 업데이트
                    q.add(new int[]{distanceList[v], v}); // 새로운 최소 거리를 우선 순위 큐에 저장
                }
            }
        }
        return distanceList;
    }
}