합승택시요금1 합승 택시 요금(Lv.3) 문제 설명 입출력 예시 요약 모든 지점을 하차지점으로 생각했을 때 각 지점에서 출발점(S), A, B 까지의 거리 중 최소값 구하기 풀이 접근 방식 1. 최소 비용 구하기 → 간선의 가중치가 1이 아니기 때문에 다익스트라 알고리즘을 통해 최소 비용 구하기 2. 하차지점 설정 → 합승을 했다면 반드시 하차지점이 생기고, 하차지점으로 부터 출발점, A도착점, B도착점까지의 거리를 계산한다. → 하차지점은 출발점(S)~하차지점, 하차지점~A, 하차지점~B 세 구간을 더한 값이 최소가 되는 노드로 설정한다. → 하차지점을 구하기 위해 모든 노드에 대해서 다익스트라 알고리즘을 실행한다. 코드리뷰 import java.util.*; // 인접 노드 번호와 간선의 가중치를 저장하기 위한 객체 클래스 class Nod.. 2024. 4. 16. 이전 1 다음