2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

문제는 프로그래머스 에서 확인 할 수 있습니다. 

 

 

풀이 : 

한 정점이 주어 졌을 때 최단거리를 구하는 문제

다익스트라 알고리즘을 사용하여 해결할 수 있다. 

 

시작정점 S와 도착지점 A, B 가 있을 때

 

시작지점을 S 라고했을 때 다익스트라 결과값,

시작지점을 A 라고했을 때 다익스트라 결과값, 

시작지점을 B 라고 했을 때 에서의 다익스트라 결과값

 

3가지를 사용해서 어느 정점을 거쳐갔을 때 최소가 되는지 확인하면 답이 나온다. 

 

 

import java.util.Arrays;

class Solution {
    static int INF = 98765432;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] w = new int[n+1][n+1];
        
        for(int i = 0; i<=n; i++) {
            Arrays.fill(w[i], INF);
        }
        
        for(int i = 0; i< fares.length; i++) {
            w[fares[i][0]][fares[i][1]] = fares[i][2];
            w[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        int[] dist;
        int[] distA;
        int[] distB;
    
        dist = dijkstra(n, w, s);
        distA = dijkstra(n, w, a);
        distB = dijkstra(n, w, b);
        
        int min = dist[a] + dist[b];
        
        // a b 들이 i 를 거쳐서 집으로 갈 때 최소값
        for(int i = 1; i<=n; i++) {
            min = Math.min(min, dist[i] + distA[i] + distB[i]);
        }
        
        return min;
    }
    
    public int[] dijkstra(int n, int[][] w, int s) {
        int dist[] = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.fill(dist, INF);
    
        dist[s] = 0;
        visited[s] = true;
    
        // s에서 인접한 점
        for(int i = 1; i<=n; i++) {
            if(!visited[i] && w[s][i] != INF) {
                dist[i] = w[s][i];
            }
        }
    
        for(int i = 0; i<n; i++) {
            int min = INF;
            int index = 0;
        
            for(int j = 1; j<=n; j++) {
                if (!visited[j]) {
                    if (min > dist[j]) {
                        min = dist[j];
                        index = j;
                    }
                }
            }
        
            visited[index] = true;
            // min 을 거쳐가는 것과 dist[j] 중 뭐가 더 빠른지
            for(int j = 1; j<=n; j++) {
                if (!visited[j] && w[index][j] != INF) {
                    dist[j] = Math.min(dist[index] + w[index][j], dist[j]);
                }
            }
        }
        return dist;
    }
}