[Swift] 2021 KAKO BLIND RECUITMENT 합승 택시 요금

 

 

Problem

 

코딩테스트 연습 - 합승 택시 요금

---

Solution

해당 문제는 Floyd Warshall 알고리즘으로 풀어야 하는 문제이다.

 

1. 모든 지점 연결하기

 

우선 모든 지점에 대한 연결을 정수에서 가장 큰 값으로 만들어준다.

 

그 다음 지점 중 자기 자신으로 연결되는 경우 1에서 1 2에서 2 3에서 3... 등은 0으로 만들어준다.

 

그리곤 주어진 fares안에 있는 연결에 대한 값을 세팅해준다.

 

2. 플로이드 와샬 알고리즘 사용하기

 

n개의 지점이 있다면 출발할 지점과 중간에 들리는 지점 도착하는 지점 이렇게 3개를 for문으로 각각 실행시켜준다.

 

이렇게 하면 중간에 거쳐가는 모든 지점에 대한 값을 알 수 있다.

 

여기서 주의할 점은 효율성을 최대화 하기 위해서 출발과 중간에 들리는 지점이 같다거나 출발과 중간이 정수의 가장 큰 값이면

 

도착지점까지 안가도 되므로 패스해준다.

 

3.가장 작은 값 찾기

 

출발지점에서 어느 지점을 거쳐야 a와 b에 도착하는 값이 가장 작은지 알아낸다.

 

(거쳐야 하는 지점 중 출발지점,a,b가 포함되어 있으므로 중간지점을 안거치는 경우도 포함되어있다.)

---

Source Code

 

---

P.S

 

처음엔 다익스트라 알고리즘으로 풀이를 했는데 정확성은 모두 맞았지만 효율성에서 모두 시간초과가 떴다.

 

그래서 질문하기를 봐봤는데 최악의 다익스트라는 O( N * ElogN ), 플로이드는 O( N3 )의 시간이 소요될 수 있다고 쓰여있었다.

 

언어에 따라서 통과되는 경우도 있지만 그렇지 않을 경우 플로이드 와샬 알고리즘으로 풀거나 다익스트라로 최선의 경우를 만들어서

 

푸는 방법이 있었는데 그냥 플로이드 와샬로 갈아탔다.

 

플로이드 와샬이 훨씬 간단하고 쉽게 구현할 수 있었다.

 

(다익스트라를 계속 효율적으로 풀어보려고 하니깐...점점 플로이드 와샬 알고리즘과 비슷해지는 느낌은....뭐지..)