카카오코테 - 합승 택시 요금

코드

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {

        int[][] price = new int[n+1][n+1];
        for (int i=0;i<price.length;i++) {
            Arrays.fill(price[i],10000000);
            price[i][i] = 0;
        }
        
        for (int i=0;i<fares.length;i++) {
            int c = fares[i][0];
            int d = fares[i][1];
            int f = fares[i][2];
            
            price[c][d] = f;
            price[d][c] = f;
        }
        
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                for (int k=1;k<=n;k++) {
                    price[j][k] = Math.min(price[j][k],price[j][i]+price[i][k]);
                }
            }
        }
        int answer = price[s][a] + price[s][b];
        
        for (int i=1;i<=n;i++) {
            answer = Math.min(answer,price[s][i] + price[i][a] + price[i][b]);
        }
        
        return answer;
    }
}

풀이

😎플로이드 와샬 알고리즘을 통해서 푼 문제입니다.

1. price라는 2차원 배열을 하나 생성합니다. (계산을 편하게 하기 위해 기존보다 +1큰 배열을 생성해줍니다.)
2. fares를 이용해 price에 fares를 통해 요금을 넣어줍니다. price[i][j]는 i에서 j로 가는 비용을 뜻 합니다.
3. 플로이드 와샬 알고리즘을 토대로 각 노드별로 최소 비용을 계산해줍니다. (플로이드 와샬 알고리즘은 다익스트라 알고리즘을 더 확장한 알고리즘이라고 이해하시면 됩니다.)
4. 이제 각 노드별 최소 거리가 구해진 상태입니다. 여기서 price[시작][첫 번째 목표] + price[시작][두 번째 목표]를 answer의 초기값으로 저장해줍니다. 그 이유는 둘 다 합승을 하지 않고 처음부터 따로따로 가는 것이 가장 큰 값이기 때문입니다.
5. price[시작][i] + price[i][a] + price[i][b]와 기존 answer을 비교하여 작은 값을 넣어줍니다. i까지 합승을 하고 나서 헤어지는 것을 표현한 식입니다.
6. answer를 반환합니다.

😭음에는 보자마자 막막했는데 거리라는 키워드를 통해 다익스트라, bfs등을 떠올리게 되었고 해당 방법으로는 각 노드별 거리를 구하는 것이 생각보다 쉽지 않다는 것을 깨닫고 플로이드 와샬 알고리즘을 떠올리게 되었습니다.

출처 : 프로그래머스 - 합승 택시 요금