[JAVA] 프로그래머스 LEVEL3 합승 택시 요금

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

프로그래머스

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 합승 택시 요금

 

난이도: LEVEL3

알고리즘 유형: 그래프 탐색 (다익스트라 / 플로이드) 

정답 코드1(플로이드)

플로이드 마샬 알고리즘을 활용했다.

문제를 읽어보면 정점의 개수가 최대 200인데 

플로이드 마샬 알고리즘의 경우 시간 복잡도를 정점의 개수를 통해서 간편하게 구할 수 있다.

O(200^3) = 8000000 충분히 통과 가능한 시간 복잡도이다.  

import java.util.*;
class Solution {
    static int answer = 1000000 * 200; // 1 <= f <= 100000
    static ArrayList<int[]>[] graph;  // 지점갯수: 3 ~ 200
    public int solution(int n, int s, int a, int b, int[][] fares) {
        // 플로이드 알고리즘 
        int [][] map = new int [n+1][n+1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(i == j) continue;
                map[i][j] = answer;
            }
        }
        for(int i = 0; i < fares.length; i++){
            int v1 = fares[i][0];
            int v2 = fares[i][1];
            int m  = fares[i][2];
            map[v1][v2] = m;
            map[v2][v1] = m;
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    if(map[i][j] > map[i][k] + map[k][j]){
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
        // 각자 따로 가는 경우 
        answer = Math.min(answer, map[s][a] + map[s][b]);
        
        // S -> A -> B
        answer = Math.min(answer, map[s][a] + map[a][b]);
        
        // S -> B -> A
        answer = Math.min(answer, map[s][b] + map[b][a]);
        
        // S -> ?  + (? -> A) + (? -> B)
        for(int i = 1; i <= n; i++){
            if(i == a || i == b) continue;
            answer = Math.min(answer, map[s][i] + map[i][a] + map[i][b]);
        }
        
        return answer;
    }
}

정답 코드2(다익스트라)

다익스트라 보다 플로이드가 더 효율적일듯해서 문제를 플로이드로 먼저 풀었었는데 

다익스트라로도 충분히 통과가 가능할듯해서 풀어보았다.

 

다익스트라는 특정 정점에서 모든 다른 정점까지의 최단 거리를 구하는 상황에서 효율적이지만 

지금 문제와 같이

 

1번 다익스트라 

시작 정점 → A 도착 정점 + 시작 정점 → B 도착 정점

 

2번 다익스트라 

시작 정점 → 1 ~ 200 사이의 정점 + 

1 ~ 200 사이의 정점 → A  + 1 ~ 200 사이의 정점 → B

 

이렇게 2번 필요한 상황에서는 비효율적이라고 생각한다.

import java.util.*;
class Solution {
    ArrayList<int[]>[] graph;
    static final int max = 100000 * 200; // 1 <= f <= 100000 , 3 <= n <= 200
    static int answer = max;
    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 v1 = fares[i][0];
            int v2 = fares[i][1];
            int m  = fares[i][2]; // 요금 
            graph[v1].add(new int []{v2, m}); // 양방향 그래프 
            graph[v2].add(new int []{v1, m});
        }
        
        // s -> 모든 지점 다익스트라 시작 
        int [] distance = new int [n+1];
        Arrays.fill(distance, max);
        PriorityQueue<int [] > pq = new PriorityQueue<>((o1,o2) -> {
           return o1[1] - o2[1];  // 누적 거리가 적은 순서대로  
        });
        
        distance[s] = 0;
        pq.add(new int []{s, 0}); // 시작 지점 pq 삽입
        
        while(!pq.isEmpty()){
            int [] cur = pq.poll();
            if(distance[cur[0]] != cur[1]) continue; // 기록된 최단거리가 아닌 경우 continue
            for(int i = 0; i < graph[cur[0]].size(); i++){
                int [] next = graph[cur[0]].get(i);
                if(distance[next[0]] > distance[cur[0]] + next[1]){
                    distance[next[0]] = distance[cur[0]] + next[1];
                    pq.add(new int []{next[0], distance[cur[0]] + next[1]}); // pq 추가 
                }
            }
        }
        // 각자 택시 경우 answer 갱신
        answer = Math.min(answer, distance[a] + distance[b]);
        
        // S -> I  + I -> A + I -> B
        for(int i = 1; i <= n; i++){ // 중간 지점 잡기 
            if(i == s) continue;
            int sum = 0;
            sum = distance[i];
            // 다익스트라 추가로 진행 i -> A and i -> B
            int [] record = new int [n+1];
            Arrays.fill(record, max);
            record[i] = 0;
            // pq 재활용 + 리팩토링한다면 다익스트라를 스테틱 메서드로 빼서 재활용 
            pq.add(new int []{i, 0}); 
            while(!pq.isEmpty()){
                int [] cur = pq.poll();
                if(record[cur[0]] != cur[1]) continue; // 기록된 최단거리가 아닌 경우 continue
                for(int j = 0; j < graph[cur[0]].size(); j++){
                    int [] next = graph[cur[0]].get(j);
                    if(record[next[0]] > record[cur[0]] + next[1]){
                        record[next[0]] = record[cur[0]] + next[1];
                        pq.add(new int []{next[0], record[cur[0]] + next[1]}); // pq 추가 
                    }
                }
            }
            sum += record[a];
            sum += record[b];
            answer = Math.min(answer, sum);
        }
        return answer;
    }
}