프로그래머스(카카오 기출) | LV.3 합승 택시 요금 - 플로이드 or 다익스트라 문풀 (Java)

⬛ 프로그래머스(카카오 기출) | LV.3 합승 택시 요금 - 플로이드 or 다익스트라 문풀

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

그림1

그림2

문제를 보자마자 다익스트라나 플로이드를 떠올렸고, 실제로 두 방식으로 다 풀 수 있는 문제였다.

첫 시도 때는 시작점이 고정되어 있어서 다익스트라를 시도해볼까 하다가, 경유지가 다양하게 존재할 수 있기 때문에 편하게 플로이드로 all-to-all 최단 거리를 먼저 구해놓고, 편하게 모든 경유지를 거쳐서 갱신되는 최단 거리를 구하고자 했다.

---

1. '플로이드' 로 풀어보기 

💚문제 접근 방식 - 플로이드

합승의 개념은 s→(특정 경유지) 까지의 거리를 2번 더하지 않는 것으로 녹여서 풀면 될 것이라 생각했다.

그리고 처음에 풀 때는 목적지인 a와 b를 제외한 경유지에 대해서만 따지려고 a, b 만날 경우에는 무시하고 남은 지점에 대한 경유지 최단 거리를 구하고자 헀는데, 3번째 케이스가 틀렸다고 나왔다. 이유는 a나 b 중에서 경유지가 되는 최단 거리가 있어서였다. 

따라서 모든 지점을 경유지가 될 수 있다고 생각하고 풀었다.

   (1) 2차원 map 데이터 초기화

   (2) 양방향 간선 정보 담기

   (3) 플로이드 적용하여 모든 정점 간의 최단 거리 세팅

   (4) for문으로 모든 정점 순회하면서 s에서 갈 수 있는 모든 경유지와 그때 경유지에서 a와 b로 가는 값을 합산한 경로 중 최솟값을 정답으로 갱신하면 해결되는 문제이다.

💚 제출 코드 | 플로이드 풀이

import java.util.*;

class Solution {
    private static int[][] map;
    
    //솔루션 함수 
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        map = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            Arrays.fill(map[i], 1000001);
            map[i][i] = 0;
        }

        for(int[] x : fares){
            int c = x[0];
            int d = x[1];
            map[c][d] = x[2];
            map[d][c] = x[2];
        }
        
        //플로이드
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    
        
        int answer = map[s][a] + map[s][b];
        //경유지점을 다른 지점 하나씩 해보기 
        for(int k=1; k<=n; k++){
            answer = Math.min(answer, map[s][k] + map[k][a] + map[k][b]);
        }
        
        return answer;
    }
}

💚 시간복잡도 | 플로이드

• 플로이드는 O(n^3) 시간복잡도를 가진다. 이 문제의 경우 지점 n이 200까지가질 수 있어서 플로이드 알고리즘으로 잡아먹는 최악의 시간복잡도는 200^3 = 800만 정도 된다. 나머지는 플로이드 만큼 잡아먹을 시간복잡도가 없어서 대략적으로 생각했을 때 시간 내에 동작하는 것을 알 수 있다.

---

2. '다익스트라' 로 풀어보기 

💚문제 접근 방식 - 다익스트라

• 다익스트라로 풀 때도 비슷한 방식이긴 하다

1) 데이터 초기화 : 이 경우 인접리스트로 graph에 양방향 간선 담았다.

2) 시작점은 어쨋든 쓰이기 때문에 '다익스트라 함수'를 구현해놓고, s 시작점에 대한 distance[] 를 반환받았다.

3) int answer = (s→a) + (s→b) // 즉, 합승 없이 가는 가격으로 담아둔다.

4) for문으로 모든 정점에 대하여 (경유지 하나씩 해보면서) s→ 경유지 → a 와 b로 가는 최단 경로 (택시값 최소)를 반복해서 갱신한 뒤, 리턴해주면 된다.

💚 제출 코드 | 다익스트라 풀이

import java.util.*;

class Edge implements Comparable<Edge> {
    int e, val;
    Edge(int e, int val){
        this.e = e;
        this.val = val;
    }
    public int compareTo(Edge x){
        return this.val - x.val;//가중치 오름차순 정렬 
    }
}
class Solution {
    private static ArrayList<ArrayList<Edge>> graph;
    
    //dikjstra
    private static int[] dijkstra(int n, int s){
        int[] distance= new int[n+1];
        Arrays.fill(distance, 1000001);
        PriorityQueue<Edge> pQ = new PriorityQueue<>();//자동 정렬 
        //시작점 처리
        distance[s] = 0;
        pQ.offer(new Edge(s, 0));
        
        while(!pQ.isEmpty()){
            Edge cur = pQ.poll();
            if(distance[cur.e] < cur.val) continue;//기존 distance보다 큰 경우 돌 필요 없음
            
            for(Edge nx : graph.get(cur.e)){
                if(distance[nx.e] > distance[cur.e] + nx.val ){
                    distance[nx.e] = distance[cur.e] + nx.val;
                    pQ.offer(new Edge(nx.e, distance[nx.e]));
                }
            }
        }
        return distance;
    }
    
    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 [] x : fares){
            int c = x[0];
            int d = x[1];
            int v = x[2];
            //양방향
            graph.get(c).add(new Edge(d, v));
            graph.get(d).add(new Edge(c, v));
        }
        
        //다익스트라 호출 
        int[] startTarget = dijkstra(n, s);//s -> all 정보 담기 
        
        int answer = startTarget[a] + startTarget[b];//최초값은 (합승없이) a, b로 가는 비용
        
        for(int i=1; i<=n; i++){
            //다른 모든 경유지에 대하여 최단 거리 발견하는지 확인할 것 
            int[] dist = dijkstra(n, i);
            answer = Math.min(answer, startTarget[i] + dist[a] + dist[b]);
        }
        
        return answer;
    }
}

💚 시간복잡도 | 다익스트라

• 다익스트라는 인접 행렬로 구현하면 시간복잡도가 O(V^2)이고, 인접 리스트로 구현하면 O(ElogV) 이다. 나는 인접 리스트로 구현하였다.
• 이 문제에서 노드는 최대 200개이고, fares (간선 정보)는 최대 200*199/2 = 19,900개 이다.
• 대략 O(ElogV) = O(19900 log 200) 정도여서 ⇒ O(45870) 정도라고 한다.
• 다만, 찾아보니 플로이드의 경우 1번의 알고리즘으로 all-to-all 되어 그 값을 활용하면 되는데,
• 다익스트라 함수 호출은 모든 정점을 경유지라 생각하고 매번 호출시키기 떄문에 n번만큼 다익스트라 돌린 시간복잡도가 발생해서 O(n^3 logn) 정도가 된다고 한다.
• 이 문제의 경우 데이터 크기가 엄청 큰 편은 아니여서 돌아갔다.

💚 회고

• 카카오 기출이고 lv3 라고 기죽지 말고 소신껏 문제 제대로 읽고 하라는 대로 풀면 된다. 그리고 이 문제의 경우, 효율성과 정확성 테스트를 각각 처리해서 최종 정답 처리가 된다. 시간복잡도를 잘 생각해야 한다.