프로그래머스 : 합동 택시 요금 - Level 3

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

프로그래머스

1. 문제 설명

최단 거리 구하는 문제이며, 한명이 가는 길이 아닌, 두명이 택시를 타고 가는길에 어디까지 같이 가고 어디까지 따로 가야 최소 비용이 나오는가에 대한 문제이다.

 

2. 문제 풀이

최단 거리, 최소 비용인 만큼 다익스트라 알고리즘을 사용

이를 위해 PriorityQueue 사용

• fares로 인접 행렬 생성
• 출발 지점으로부터 모든 정점 까지 최소 비용을 다익스트라로 구하기 → together
• 정점을 for문으로 돌며 해당 정점으로부터 모든 정점까지 최소 비용을 다익스트라로 구하기 → alone
• together[i] + alone[a-1]  + alone[a-1]로 둘의 총 택시비를 계산하여 최솟 값 구하기
• 즉, 출발 지점부터 함께 택시 타고간 정점 까지의 비용 + 어피치 혼자 택시탄 비용 + 무지 혼자 택시탄 비용을 계산하는 것