728x90
programmers.co.kr/learn/courses/30/lessons/72413
문제 요약
- 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 지점 까지의 최단거리를 구해야 하므로 플로이드-워샬로 푸는 것이 나을 것 같아 수정하였다. 카카오 해설을 참고했다 )
반응형
'코딩 문제 풀기 ( Algorithm problem solving ) > 프로그래머스 ( Programmers )' 카테고리의 다른 글
[프로그래머스(Programmers)][자바(java)] (Lv3) 카드 짝 맞추기 (0) | 2021.03.15 |
---|---|
[프로그래머스(Programmers)][자바(java)] (Lv3) 스티커 모으기(2) (0) | 2021.03.08 |
[프로그래머스(Programmers)][자바(java)] (Lv2) 게임 맵 최단거리 <찾아라 프로그래밍 마에스터> (0) | 2021.03.08 |
[프로그래머스(Programmers)][자바(java)] (Lv3) 블록 이동하기 (0) | 2021.03.01 |
[프로그래머스(Programmers)][자바(java)] (Lv3) 기둥과 보 설치 (0) | 2021.02.28 |