[프로그래머스] 합승택시요금 (lv3)

programmers.co.kr/learn/courses/30/lessons/72413

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

 

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<fares.length; i++) {
    		// 택시요금
    		map[fares[i][0]][fares[i][1]] = fares[i][2];
    		map[fares[i][1]][fares[i][0]] = fares[i][2];
    	}
    	
    	for(int i=1; i<n+1; i++) {
    		for(int j=1; j<n+1; j++) {
    			if(map[i][j] == 0 && (i!=j)) {
    				map[i][j] = 1000000;
    			}
    		}
    	}
    	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(map[i][j] > map[i][k] + map[k][j] ) {
    					map[i][j] = map[i][k]+ map[k][j];
    				}
    			}
    		}
    	}
    	
    	int answer = Integer.MAX_VALUE;
    	for(int i=1; i<n+1; i++) {
    		int sum = map[s][i];
    		sum+= map[i][a];
    		sum+= map[i][b];
    		answer = Math.min(answer, sum);
    	}
        return answer;
    }
}

소요시간: 30분

플로이드 와샬을 이용해서 푸는 문제였다.

카카오 블라인드 테스트 칠 때는 조급한 마음이었어서 생각이 안났었는데

스타트지점에서 각 점을 순회하면서 그 점까지의 최단거리를 더하고

그 점에서 a와 b의 도착지점까지의 최단거리를 더하면 풀린다.

생각보다 간단한 문제였다.!