[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금
유형
- 그래프
- 최단거리 탐색 (다익스트라, 플로이드 워셜)
문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다.
문제 풀이
그래프에서 최단 경로를 구하는 “dijkstra 알고리즘”, 또는 “Floyd-Warshal 알고리즘”을 사용하면 풀 수 있는 문제입니다.
이중 플로이드 알고리즘을 사용하여서 문제를 푼다고 가정하면, 다음과 같이 모든 지점 사이의 최저 예상 택시요금을 구할 수 있습니다.
d[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금
그 다음, 다음과 같이 루프를 돌면서 최솟값을 찾아주면 됩니다.
문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)
다익스트라나, 플로이드 워셜 알고리즘에 대한 지식이 필요한 문제였다.
코드
import java.util.Arrays;
class Solution {
static int[][] dist;
static final int INF = 20000001;
//n 지점개수, s 출발지점, a A도착지점, b B도착지점, fares 택시요금
public int solution(int n, int s, int a, int b, int[][] fares) {
dist = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], INF);
dist[i][i] = 0;
}
for (int i = 0; i < fares.length; i++) {
dist[fares[i][0]][fares[i][1]] = fares[i][2];
dist[fares[i][1]][fares[i][0]] = fares[i][2];
}
//플로이드 알고리즘 이용
findMinPath(n);
//문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)
int answer = Integer.MAX_VALUE;
for (int k = 1; k <= n; k++) {
if (dist[s][k] != INF && dist[k][a] != INF && dist[k][b] != INF) {
answer = Math.min(answer, dist[s][k] + dist[k][a] + dist[k][b]);
}
}
return answer;
}
private static void findMinPath(int n) {
//dist[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
Author And Source
이 문제에 관하여([2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@titu/2021-KAKAO-BLIND-RECRUITMENT-합승-택시-요금저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)