kakao 블라인드 코딩테스트 1차 - 합승택시 JAVA

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

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

 

[문제]

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

 

- 경로탐색 문제

플로이드 와샬 : 그래프에서 '모든 정점' → '모든 정점' 까지의 최단 경로를 구하는 알고리즘

이 플로이드 와샬만으로도 통과 가능한 듯 하다. ( O(N^3) 이므로, 제한범위 3<=n<=200에 따라 200^3 = 8,000,000 번 안에 해결 )

 

[풀이]

다익스트라(dijkstra Algorithm)를 통해 출발점 s와 a,b의 모든 정점 사이의 거리를 구함.

 

다익스트라 알고리즘 Java 구현은 설명을 아래 링크를 참조

https://bumbums.tistory.com/4

자바로 만드는 다익스트라 (dijkstra) 알고리즘

 

 

다익스트라로부터 구해진 s,a,b를 바탕으로 일정 지점까지 합승해서 가는 거리값과 합승하지 않고 가능 notSharing 값을 비교해서, 최솟값(min)을 찾아 return 

 

[Java 코드]