알고리즘/programmers

[Programmers] 합승 택시 요금

꾸준함. 2022. 7. 9. 10:41

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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

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

 

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

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

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

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

3. answer를 반환합니다.


 

개발환경: Programmers IDE

 

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

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 표 편집  (0) 2022.07.09
[Programmers] 금과 은 운반하기  (0) 2022.07.09
[Programmers] 최적의 행렬 곱셈  (0) 2022.06.25
[Programmers] 사라지는 발판  (0) 2022.06.25
[Programmers] 불량 사용자  (0) 2022.06.25