[프로그래머스/Java] 72413번 합승 택시 요금
프로그래머스 합승 택시 요금 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72413
문제를 요약하면 다음과 같다.
'S에서 X까지 가는 최소 요금 + X에서 A까지 가는 최소 요금 + X에서 B까지 가는 최소 요금'이 최소가 되는 X를 찾아 이 요금을 계산하여라.
여기서 X는 A와 B가 각자의 길을 가게 되는 지점일 것이다.
최소가 되는 X를 찾아야 하기 때문에, X에 1부터 n까지 모두 대입해보아야 한다.
X에서 Y로 가는 최소비용과 Y에서 X로 가는 최소비용이 동일하다는 것도 잊지 말자.
따라서 S, A, B에서 각 정점까지 가는 데 드는 최소 비용을 모두 구해야 하고,
결국 임의의 정점 Y에서 각 정점까지 가는 데 드는 최소 비용을 구하는 메소드를 만들어야 한다.
처음에는 DFS로 완전탐색을 구현했다가 시간초과에 걸리고 말았다.
그래서 시도한 것이 다익스트라(Dijkstra) 알고리즘.
다익스트라는 한마디로 '한 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘'이다.
다익스트라 메소드를 구현한 뒤, S, A, B 각각에 대해 수행하였다.
class Solution {
static final int maxFee = 100_000;
public int solution(int n, int s, int a, int b, int[][] fares) {
final int[][] graph = new int[n+1][n+1];
final int maxTotalFee = maxFee*(n-1);
int answer = maxTotalFee*3;
for(int[] tmp : fares)
graph[tmp[0]][tmp[1]] = graph[tmp[1]][tmp[0]] = tmp[2];
int[][] distance = new int[3][n+1];
dijkstra(s, n, maxTotalFee, graph, distance[0]);
dijkstra(a, n, maxTotalFee, graph, distance[1]);
dijkstra(b, n, maxTotalFee, graph, distance[2]);
for(int i = 1 ; i <= n ; i++)
answer = Math.min(answer, distance[0][i] + distance[1][i] + distance[2][i]);
return answer;
}
public void dijkstra(int x, int n, int maxTotalFee, int[][] graph, int[] distance){
boolean[] check = new boolean[n+1];
for(int i = 1 ; i <= n ; i++)
distance[i] = maxTotalFee;
check[x] = true;
distance[x] = 0;
for(int i = 1 ; i <= n ; i++)
if(graph[x][i] > 0) distance[i] = graph[x][i];
int minTotalFee;
int minIndex;
do {
minTotalFee = maxTotalFee+1;
minIndex = -1;
for(int i = 1 ; i <= n ; i++){
if(!check[i] && distance[i] < minTotalFee){
minTotalFee = distance[i];
minIndex = i;
}
}
if(minIndex >= 0){
check[minIndex] = true;
for(int i = 1 ; i <= n ; i++){
if(!check[i] && graph[minIndex][i] > 0)
distance[i] = Math.min(distance[i], minTotalFee + graph[minIndex][i]);
}
}
} while (minTotalFee <= maxTotalFee);
}
}
.
.
모든 정점 사이의 최단거리를 구하는 '플루이드 와샬(Floyd Warshall)' 알고리즘도 이 문제에 적용 가능하다고 한다.
언젠가 이 알고리즘을 적용한 문제도 소개할 수 있기를.
Author And Source
이 문제에 관하여([프로그래머스/Java] 72413번 합승 택시 요금), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@weaxerse/프로그래머스Java-72413번-합승-택시-요금저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)