[프로그래머스] 합승 택시 요금 / 2021 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 합승 택시 요금 / 2021 KAKAO BLIND RECRUITMENT

코딩테스트 연습 - 합승 택시 요금

 

📝 풀이 과정

모든 정점 간의 거리를 구할 수 있는 플로이드 와샬을 사용했다. 플로이드 와샬의 시간 복잡도는 $O(n^3)$이지만, 정점의 개수가 200개이기 때문에 충분하다.

 

먼저 플로이드 와샬 알고리즘을 통해 모든 정점간의 거리를 구하고, s → a + s → b로 answer 값을 초기화 하였다.
두 사람이 s에서 택시를 타고 i에서 내린 뒤 각자의 집으로 간다고 하면, s → i + (i → a + i → b)로 답을 구할 수 있고 모든 정점을 돌며 최소값을 갱신해가면 답을 구할 수 있다.

 

⏱ 시간 복잡도

플로이드 와샬의 시간 복잡도는 $O(n^3)$, 합승 지점을 검사하는 시간 복잡도는 $O(n)$이 중첩으로 이루어져 있지 않기 때문에 최종적으로 $O(n^3)$이 된다

 

💻 코드

import java.util.Arrays;

class Solution {
    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++) {
            Arrays.fill(map[i], 100_000_000);
            map[i][i] = 0;
        }
        for (int[] fare : fares)
            map[fare[0]][fare[1]] = map[fare[1]][fare[0]] = fare[2];

        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];

        int answer = map[s][a] + map[s][b];

        for (int i = 1; i <= n; i++) 
            answer = Math.min(answer, map[s][i] + map[i][a] + map[i][b]);


        return answer;
    }
}