카카오 블라인드 2021) 합승 택시 요금

합승 택시 요금

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

플로이드-와샬을 이용해서 쉽게 풀 수 있었다.

주어진 각 구간마다의 요금을 플로이드-와샬을 통해, 연결된 구간을 이동하는데 최소 비용을 저장해주었다.

이후, 문제에서 요구하는 답인, 출발지 s에서 시작해 k를 경유하여, 각각 a와 b 목적지로 가는 비용의 최소를 구해주었다.

 

최근에 플로이드 와샬 문제를 많이 풀어서, 크게 어렵지 않게 풀 수 있었다.

 

코드

 

import java.util.Arrays;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] map = initMap(n,fares);
        floydWarshal(n,map);
        return getMinCost(map,n, s, a, b);
    }
    
    private int getMinCost(int[][] map, int n, int s, int a, int b) {
        int answer = Integer.MAX_VALUE;
        for(int k=1; k<=n; k++) { // 문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)
          answer = Math.min(answer, map[s][k]+ map[k][a] + map[k][b]);
        }
        return answer;
    }
    
    private void floydWarshal(int n, int[][] map) {
        for(int k=1; k<=n; k++) {
          for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
              if(i!=j && map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE) {
                map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
              }
            }
          }
        }
    }
    
    private static int[][] initMap(int n, int[][] fares) {
        int[][] map = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
          Arrays.fill(map[i], Integer.MAX_VALUE);
          map[i][i] = 0;
        }

        for(int[] fare : fares) {
          map[fare[0]][fare[1]] = fare[2];
          map[fare[1]][fare[0]] = fare[2];
        }

        return map;
    }
}