알고리즘
[Programmers]합승 택시 요금
Lahezy
2022. 9. 23. 14:48
728x90
[문제 링크]
https://school.programmers.co.kr/learn/courses/30/lessons/72413
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[생각 흐름]
플로이드워셜 알고리즘이용
start에서 i까지 같이 가고 i 부터 a,b까지 가는 경로
[코드]
import java.util.Arrays;
public class Main {
public int solution(int n, int s, int a, int b, int[][] fares) {
int arr[][] = new int[n+1][n+1];
int INF = (int) 1e9;
//배열 초기화 (자기자신 가는 방법은 0 )
for (int i = 0; i <= n; i++) {
Arrays.fill(arr[i], INF);
arr[i][i]=0;
}
for (int i = 0; i < fares.length; i++) {
int[] temp = fares[i];
int e1 = temp[0];
int e2 = temp[1];
int w = temp[2];
arr[e1][e2] = arr[e2][e1] = w;
}
StringBuilder sb = new StringBuilder();
//플로이드 워셜
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = Math.min(arr[i][p] + arr[p][j], arr[i][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (arr[i][j] == INF) sb.append("INF ");
else sb.append(arr[i][j] + " ");
sb.append("\n");
}
System.out.println(sb);
int answer = arr[s][a]+arr[s][b];
for(int i=1;i<=n;i++){
int tempMin = arr[s][i]+arr[i][a]+arr[i][b];
if(tempMin<=0) continue;
answer = Math.min(tempMin,answer);
}
return answer;
}
}
728x90