[프로그래머스(Programmers)][자바(java)] (Lv3) 합승 택시 요금

728x90

 

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

 

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

6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

programmers.co.kr

 

문제 요약

  • A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.
  • 지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다.
    ( fares 배열의 각 행은 [c, b, f] 형태 )
  • 만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

 

문제 풀이

*  플로이드-워샬 알고리즘 ( 모든 쌍 최단거리 알고리즘 )

-  매개변수들 중 택시 요금 배열( int fares[] )로 그래프의 간선 배열( int e[][] )( e : edge ) 생성
  ( 방향성이 없으므로 e[c][d] = e[d][c] = f 이다 )

-  그래프의 간선 배열들로 플로이드-워샬 알고리즘을 통해 모든 쌍의 최단거리 배열( int d[][] ) 생성

-  택시에 합승한 최소 요금을 구하려면 시작점( s )에서 어느 지점( k )까지의 요금, 그 지점에서 각각 a, b 까지의 요금을 모두 더한 값이 최소인 값을 구해야 함

-  루프를 돌며 d[s][i]+d[i][a]+d[i][b] 의 최솟값을 구해 return

class Solution {
    
    int max;
	
	public int[][] floydWarshall( int d[][], int e[][], int n ) {
		int i, j, k;
		for( i = 1; i <= n; i++ ) 
			for( j = 1; j <= n; j++ )
				if( i != j )
					d[i][j] = e[i][j] == 0 ? max : e[i][j];
		for( k = 1; k <= n; k++ )
			for( i = 1; i <= n; i++ )
				for( j = 1; j <= n; j++ )
					if( d[i][j] > d[i][k] + d[k][j] )
						d[i][j] = d[i][k] + d[k][j];
		return d;
	}
	
	public int solution(int n, int s, int a, int b, int[][] fares) {
		int d[][] = new int[n+1][n+1];	// vertex ( distance )
		int e[][] = new int[n+1][n+1];	// edge
		int nf = fares.length; 
		int i, u, v;
		for( i = 0; i < nf; i++ ) {
			u = fares[i][0];
			v = fares[i][1];
			e[u][v] = e[v][u] = fares[i][2];
		}
		max = n*100000;
		d = floydWarshall( d, e, n );
		int res = max, sum;
		for( i = 1; i <= n; i++ ) {
			sum = d[s][i] + d[i][a] + d[i][b];
			if( res > sum )
				res = sum;
		}
		return res;
	}
}

( 처음에 다익스트라로 풀어보려다가 시작점( s )에서부터 어느 한 지점까지는 a,b가 같이 간 후 그 지점에서 각각 a, b 지점 까지의 최단거리를 구해야 하므로 플로이드-워샬로 푸는 것이 나을 것 같아 수정하였다. 카카오 해설을 참고했다 ) 

 

 

반응형