[프로그래머스][합승 택시 요금]-Lv.3

🎃문제

🎃접근방법

1. 처음에 다익스트라 접근을 하였다. 하지만 끝내 풀지 못해서 풀이과정을 봤는데 다익스트라 방식 말고도 플로이드 와샬 알고리즘 방법을 사용해서 푼 방식도 있었다.

🎃코드(다익스트라)

import java.util.*;
class Solution {
    static int INF = Integer.MAX_VALUE;
    static ArrayList<Node>[] graph;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        graph = new ArrayList[n+1];

        // 그래프 초기화
        for(int i=1; i<=n; i++){
            graph[i] = new ArrayList<>();
        }
        // 그래프 연결
        for(int i=0; i<fares.length; i++){
            int from = fares[i][0];
            int to = fares[i][1];
            int value = fares[i][2];

            graph[from].add(new Node(to, value));
            graph[to].add(new Node(from, value));
        }
        int[] startA = new int[n+1];
        int[] startB = new int[n+1];
        int[] startS = new int[n+1];

        Arrays.fill(startA,INF); 
        Arrays.fill(startB,INF);
        Arrays.fill(startS,INF);

        startA = shortPath(a, startA);
        startB = shortPath(b, startB);
        startS = shortPath(s, startS);
        int answer = INF;
        for(int i=1; i<=n; i++){
            answer = Math.min(answer, startA[i] + startB[i] +startS[i]);
        }

        return answer;
    }
    static int[] shortPath(int start, int[] distance){
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>(){
            @Override
            public int compare(Node n1, Node n2){
                return Integer.compare(n1.dis, n2.dis);
            }
        });
        distance[start] = 0;
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node now = pq.poll();

            if(now.dis > distance[now.num]) continue;

            for(Node next : graph[now.num]){
                if(distance[next.num] > distance[now.num] + next.dis){
                    distance[next.num] = distance[now.num] + next.dis;
                    pq.add(new Node(next.num, distance[next.num]));
                }
            }
        }
        return distance;
    }
    static class Node{
        int num;
        int dis;
        public Node(int num, int dis){
            this.num = num;
            this.dis = dis;
        }
        public String toString(){
            return "["+num+", "+dis+"]";
        }
    }
}

🎃코드(플로이드 와샬)

import java.util.*;
class Solution {
    static int INF = 20000001;
    static int[][] graph;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        graph = new int[n+1][n+1];
        // 그래프 초기화
        for(int i=1; i<=n; i++){
            Arrays.fill(graph[i],INF);
            graph[i][i] = 0;
        }
        // 그래프 연결
        for(int i=0; i<fares.length; i++){
            int from = fares[i][0];
            int to = fares[i][1];
            int value = fares[i][2];
            
            graph[from][to] = value;
            graph[to][from] = value;
        }
        
        for(int k=1; k<=n; k++){ //  거쳐가는 노드
            for(int i=1; i<=n; i++){ 
                for(int j=1; j<=n; j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        int answer = graph[s][a] + graph[s][b];
        for(int i=1; i<=n; i++){
            answer = Math.min(answer, graph[s][i] + graph[i][a] + graph[i][b]);
        }
        return answer;
    }
}

🎃 느낀점

다익스트라에 비해 플로이드와샬를 구현하는게 더 코드가 짧고 깔금하게 느껴졌다.
1. 모든 정점들이 다른 정점들과 비교해서 최적의 거리를 구하는 것은 플로이드 와샬을 쓰는것이 유리하고
2. 정해진 Start에서 최적의 거리를 구할때에는 다익스트라가 유리하다고 느껴졌다.

🎃 알고 넘어가기

우선순위 큐 클래스(객체)를 넣었을 때 3가지 방법

// 방법 1. 
PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>(){
	@Override
	public int compare(Node n1, Node n2){
		return Integer.compare(n1.dis, n2.dis);
	}
});
// 방법 2.
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.dis,o2.dis));
// 방법 3.
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dis));