합승 택시 요금(프로그래머스) JAVA

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

프로그래머스

 

문제설명

무지와 어피치가 같이 택시를 타고 집에 간다. 무지의 집은 B고 어피치의 집은 A이다. 

S에서 시작해서 목적지 A와 B까지 도착할 때 최소 비용을 구하는 문제이다.

• 이 문제가 다른 문제랑 다른 점은 택시를 같이 타고 가다가 내릴 수 있다는 점이다.
• 위 문제에서 최소 비용의 예를 생각해 보자
• 4번에서 시작해서 5번까지는 둘이 택시를 같이 탄다. 그러면 34원
• 그리고 B, A까지 각각 택시를 타고 간다.
• 34 + 2 + (24+22) = 82원 -> 82원이 최소 비용이다.
• S에서 각각 택시를 타고가면 66 + 50 =  116원이 나온다. 

 

문제에 대한 아이디어 및 구현

제일 처음 보고 최소 비용이니깐 디익스트라로 해결을 해야하나 고민했다.

디익스트라로 풀면 택시를 같이 타는 부분을 어떻게 구현해야 할지 생각이 잘 안떠올랐다. 

그래서 생각해낸 방법이 출발점이 S부터 둘이 나누어지는 지점을 먼저 찾아야 겠다고 생각했다.

즉, 2명이 타고 가는게 아니라 한명이 타고 가다가 A와 B지점으로 각각 가야 한다고 생각했다.

 

플로이드 와샬로 모든 지점의 최소 비용 찾기

결국 우리가 찾아야 할 것은(s -> 특정 지점 + 특정 지점 -> a + 특정 지점 -> b) 의 최소값이다. 그러므로 플로이드 와샬로 각각의 노드에서 다른 노드까지의 최소 지점을 모두 찾으면 쉽게 풀 수 있을거 같다고 생각했다.

근데 문제 위에 효율성 테스트를 한다고 적혀있었다. 그러면 플로이드 와샬은 시간 복잡도가 n^3이니깐 사용하면 안되나 잠깐 고민했다.

n의 갯수가 200개 이하인 것을 보고 이건 써도 괜찮겠다고 생각했다. 

        int answer = 0;
        dp = new int[n+1][n+1];
        for(int i = 0; i <=n; ++i){
            for(int j = 0; j<=n; ++j){
                if(i == j) dp[i][j] = 0;
                else dp[i][j] = 987654321;
            }
        }
        for(int i = 0; i < fares.length; ++i){
            int u = fares[i][0]; 
            int v = fares[i][1];
            int w = fares[i][2];
            dp[u][v] = w;
            dp[v][u] = w;
        }
        int result = Integer.MAX_VALUE;
        //플로이드 와샬로 모든 최소 비용 찾기
        for(int m = 1; m <= n; m++){
            for(int st = 1; st <= n; st++){
                for(int e = 1; e <= n; e++){
                    if(dp[st][m] + dp[m][e] < dp[st][e]) {
                        dp[st][e] = dp[st][m] + dp[m][e];
                    }
                }
            }
        }

 

점화식으로 답 구하기

result = Math.min(result, dp[s][a] + dp[s][b]); // 출발점에서 각각 텍시를 바로 타고 갈때 
        for(int i = 1; i<= n; ++i){
            if(dp[s][i] < 0 || dp[s][i] == 987654321) continue; // 갈 수 없는 지점 넘어가기
            result = Math.min(result, dp[s][i] + dp[i][a] + dp[i][b]);
        }

 

전체 코드

class Solution {
    int dp[][];
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        dp = new int[n+1][n+1];
        for(int i = 0; i <=n; ++i){
            for(int j = 0; j<=n; ++j){
                if(i == j) dp[i][j] = 0;
                else dp[i][j] = 987654321;
            }
        }
        for(int i = 0; i < fares.length; ++i){
            int u = fares[i][0]; 
            int v = fares[i][1];
            int w = fares[i][2];
            dp[u][v] = w;
            dp[v][u] = w;
        }
        int result = Integer.MAX_VALUE;
        for(int m = 1; m <= n; m++){
            for(int st = 1; st <= n; st++){
                for(int e = 1; e <= n; e++){
                    if(dp[st][m] + dp[m][e] < dp[st][e]) {
                        dp[st][e] = dp[st][m] + dp[m][e];
                    }
                }
            }
        }
        result = Math.min(result, dp[s][a] + dp[s][b]);
        for(int i = 1; i<= n; ++i){
            if(dp[s][i] < 0 || dp[s][i] == 987654321) continue;
            result = Math.min(result, dp[s][i] + dp[i][a] + dp[i][b]);
        }
        return answer = result;
    }
}