[프로그래머스] 카카오_합승 택시 요금 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/72413?language=java 

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

 

풀이

이 문제는 접근법만 알면 간단한 문제이다. 예전에 이 문제를 푼 적이 있는데, 너무 어렵게 생각해서 매우 어려운 문제인 줄 알았다. 하지만 이 문제는 간단한 해결법이 존재한다.

 

우선, 이 문제는 n이 200이하로 매우 작다. 따라서 O(n^3)의 시간복잡도를 가진 플로이드-와샬 알고리즘을 사용해 모든 정점간의 거리를 계산할 수 있다. 이렇게 모든 정점간의 거리를 계산했다면, 이후 어디까지 합승한 뒤 따로 가는게 빠른지 계산할 수 있다.

 

플로이들-와샬 알고리즘으로 모든 정점간의 거리를 계산했다고 하자. 이후 다음과 같은 식으로 모든 정점을 합승 지점으로 계산할 수 있다.

for(int i=1; i<n+1; i++){
	if(dist[s][i] != INF && dist[s][a] != INF && dist[s][b] != INF){
		answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
	}
}

s는 시작지점 이므로, 시작지점 부터 i까지는 합승하고, i부터 a까지 가는 비용과 i부터 b까지 가는 비용이 가장 작은 값을 찾으면 되는 것이다.

 

해결법을 알고나면 간단한 문제이지만, 이러한 해결법을 생각하는게 어려운 문제였던 것 같다.

 

 

코드

import java.util.*;

class Solution {
    static final int INF = 987654321;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;
        int dist[][] = new int[n+1][n+1];
        for(int i=0; i<n+1; i++){
            Arrays.fill(dist[i], INF);
        }
        
        for(int i=0; i<fares.length; i++){
            for(int j=0; j<fares[i].length; j++){
                int c = fares[i][0];
                int d = fares[i][1];
                int f = fares[i][2];
                dist[c][d] = f;
                dist[d][c] = f;
            }
        }
        
        
        for(int k=1; k<n+1; k++){
            for(int i=1; i<n+1; i++){
                for(int j=1; j<n+1; j++){
                    if(i==j) dist[i][j] = 0;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            if(dist[s][i] != INF && dist[s][a] != INF && dist[s][b] != INF){
                answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
        
        
        return answer;
    }
}