[2021 KAKAO Blind Recruitment] Q4. 합승 택시 요금 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G5 - G4

 

알고리즘 분류

플로이드 or 다익스트라

 

풀이

그래프의 최단거리 관련 응용 문제를 조금만 풀어봤다면 풀이를 바로 알 수 있고 그렇지 않더라도 플로이드 알고리즘 혹은 다익스트라 알고리즘을 알고 있었다면 코딩 테스트 시간 내에는 풀이를 유추해낼 수 있는 문제라고 생각합니다. 헤어지는 지점을 K라고 두고 나면 요금은 dist(A, K) + dist(B, K) + dist(S, K)가 됨을 쉽게 떠올릴 수 있습니다.

 

그러면 모든 K에 대해 dist(A, K) + dist(B, K) + dist(S, K)의 최솟값을 구하면 끝입니다. V가 작기 때문에 O(V³)에 동작하는 플로이드 알고리즘을 사용해도 되고, 다익스트라 알고리즘을 시작점 A, B, S에 대해 진행하는 O(ElgE) 풀이도 통과됩니다. 물론 구현은 플로이드 알고리즘이 훨씬 간단합니다.

 

다익스트라는 이 문제에 한해서 힙을 이용한 O(ElgE) 구현보다 그냥 2중 for문을 도는 O(V²+E) 풀이가 더 효율적이지만 일반적으로는 힙을 이용하는 것이 더 좋기 때문에 힙을 이용한 구현만 코드로 작성했습니다.

 

코드(C++, 플로이드)

 

코드(C++, 다익스트라)

 

코드(Python, 플로이드)

굉장히 어이없게도 맨 처음에 Python으로 플로이드 코드를 짜서 제출했을 때 시간 초과 판정을 받았었습니다. 파이썬은 성능이 굉장히 느리기에 오른쪽과 같이 값이 갱신되지 않을 때에도 불필요한 대입 연산을 추가할 경우 시간 초과가 발생했습니다. 참고로 알아두세요.

 

코드(Python, 다익스트라)

 

코드(Java, 플로이드)

 

코드(Java, 다익스트라)

 

관련 강의

0x1D강 - 플로이드 알고리즘

0x1E강 - 다익스트라 알고리즘