[Programmers] 합승 택시 요금 (최단거리)

플로이드-워셜(Floyd-Warshall)

import java.util.*;

class Solution {
    int[][] dist;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        dist = new int[n+1][n+1];
        // 초기 거리 초기화
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) continue;
                dist[i][j] = 100_000 * n + 1;
            }
        }
        for(int i = 0; i < fares.length; i++) {
            int x = fares[i][0];
            int y = fares[i][1];
            int weight = fares[i][2];
            dist[x][y] = weight;
            dist[y][x] = weight;
        }
        
        // 플로이드 워셜 알고리즘
        // 노드를 1개부터 N개까지 k를 거쳐가는 경우를 모두 고려한다.
        for(int k = 1; k <= n; k++) {
            // 노드 i에서 j로 가는 경우
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
        
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <=n ; i++) {
            min = Math.min(dist[s][i] + dist[i][a] + dist[i][b], min);
        }
        return min;
    }
}

다익스트라(Dijkstra)

import java.util.*;

class Solution {
    ArrayList<Edge>[] edge;
    int[] dist;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        edge = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            edge[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < fares.length; i++) {
            int x = fares[i][0];
            int y = fares[i][1];
            int weight = fares[i][2];
            edge[x].add(new Edge(y, weight));
            edge[y].add(new Edge(x, weight));
        }
        
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            dist = new int[n+1];
            dijkstra(i);
            min = Math.min(dist[s] + dist[a] + dist[b], min);
        }
        
        return min;
    }
    
    public void dijkstra (int start) {
        // 모든 정점까지에 대한 거리를 무한대로 초기화 하기
        for(int i = 1; i < dist.length; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        
        // 최소 힙 생성
        PriorityQueue<Info> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
        
        // 시작점에 대한 정보(Information)을 기록에 추가하고, 거리 배열(dist)에 갱신
        pq.add(new Info(start, 0));
        dist[start] = 0;
        
        // 거리 정보들이 모두 소진될 때까지 거리 갱신
        while(!pq.isEmpty()) {
            Info info = pq.poll();
            if(dist[info.idx] < info.dist) continue;
            
            // 연결된 모든 간선들을 통해서 다른 정점들에 대한 정보를 갱신해준다.
            for(Edge e : edge[info.idx]) {
                if(dist[info.idx] + e.weight >= dist[e.to]) continue;
                
                // e.to 까지 갈 수 있는 더 짧은 거리를 찾았다면 이에 대한 정보를 갱신하고 pq에 기록
                dist[e.to] = dist[info.idx] + e.weight;
                pq.add(new Info(e.to, dist[e.to]));
            }
        }
    }
    
    class Info {
        int idx;
        int dist;
        
        public Info (int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
    
    class Edge {
        int to;
        int weight;
        
        public Edge (int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}