[Programmers] 합승 택시 요금

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

저는 다익스트라 알고리즘을 통해 푼 문제인데 정석 풀이를 보면 플로이드-와샬 알고리즘으로 푼 문제였습니다.

일단 제가 푼 코드를 기반으로 설명을 진행하고 추후에 플로이드-와샬 코드도 올리도록 하겠습니다.

 

알고리즘은 아래와 같습니다.

1. 시작점 s를 기준으로 다익스트라 알고리즘을 진행하고 그 결과를 sDistance에 저장합니다.

2. [1, n] 지점을 순회하며 각 지점을 기준으로 다익스트라 알고리즘을 진행하고 결과를 vDistance에 저장합니다.

2.1 현재 기준이 되는 지점을 v라고 했을 때 s -> v로 가는 비용, v -> a로 가는 비용, v -> b로 가능 비용의 합산이 answer보다 작을 경우 answer를 업데이트해줍니다.

3. answer를 반환합니다.

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~