LV3 [KAKAO] 합승 택시 요금

---

문제

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

프로그래머스

풀이

플로이드 알고리즘을 사용하면 금방 풀 수 있는 문제였다.

 

우선 fares를 활용하여 배열을 세팅하고, 플로이드 알고리즘을 수행한다.

그러면 노드간의 최단 경로를 얻을 수 있다.

 

이후 중요 포인트는 "택시를 어디까지 같이 타고 갈 것인가" 이다. 

 

예시를 보면 5까지 같이 타고 간 다음에 각자 택시를 타고 이동한다. 이게 단순히 s에서 a로 가는거 + s에서 b로 가는 방식보다 훨씬 싸게 먹히기 때문이다. 

 

따라서 s에서 시작하여 i라는 특정 지점까지 간 다음, 그 곳에서 해산해서 a와 b로 이동하는 시나리오로 진행해야한다. 

 

플로이드를 사용하여 각 최단 경로가 저장되어 있는 배열이 dp라고 했을 때 코드는 아래와 같다.

(MV는 길이 없음을 의미한다.)

for(int i=1; i<n+1; i++){
            if(dp[s][i] == MV || dp[i][a] == MV || dp[s][i] == MV || dp[i][b] == MV) continue;
            answer = Math.min(answer,  dp[s][i] + dp[i][a] +  dp[i][b]);
        }

시작점은 항상 고정이므로 s로 설정하고, 모든 노드(i)를 다 탐색하면서 s에서 i로 이동한 다음 그곳에서 a와 b로 각각 이동하는 것이다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        int[][] dp = new int[n+1][n+1];
        int MV = Integer.MAX_VALUE;
        int answer = MV;
        
        for(int i=1; i<n+1; i++){
            for(int j=1; j<n+1; j++){
                if(i==j) dp[i][j] = 0;
                else dp[i][j] = MV;
            }
        }
        
        for(int i=0; i<fares.length; i++){
            int x = fares[i][0];
            int y = fares[i][1];
            int v = fares[i][2];
            
            dp[x][y] = v;
            dp[y][x] = v;
        }
        
        for(int k=1; k<n+1; k++){
            for(int x= 1; x< n+1; x++){
                for(int y= 1; y< n+1; y++){
                    if(dp[x][k] == MV || dp[k][y] == MV) continue;
                    dp[x][y] = Math.min(dp[x][y], dp[x][k] + dp[k][y]);
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            if(dp[s][i] == MV || dp[i][a] == MV || dp[s][i] == MV || dp[i][b] == MV) continue;
            answer = Math.min(answer,  dp[s][i] + dp[i][a] +  dp[i][b]);
        }
        
        return answer;
    }
}

 

후기

 

문제를 대충봐서 플로이드로 풀고 왜 안되지? 이러고 있었다. 

 

레벨3이지만 알고리즘 하나만 박으면 단순하게 풀 수 있는 문제였다.

 

추가로 이 문제 풀면서 플로이드의 경로 추적도 공부하게 되었는데 참고한 링크를 첨부하겠다.

https://blog.encrypted.gg/917?category=773649 

[실전 알고리즘] 0x13강 - 플로이드 알고리즘_구버전