[Swift] 프로그래머스 2018 Summer/Winter Coding 배달

 

Problem

 

코딩테스트 연습 - 배달

---

Solution

 

해당 문제는 한 정점에서의 거리만 구하면 되기 때문에 다익스트라 알고리즘으로 풀어야 하는 문제다.

 

(플로이드로 풀면 효율적이진 않지만 풀리긴 풀린다...)

 

다익스트라 풀이

 

1.모든 거리를 저장할 이차원 배열을 만들어줌.

 

(allDistances 변수를 참고해주세요!)

 

2.다익스트라로 시작하는 정점에서 가장 가까운 거리를 찾아줌.

 

(dijkstra 함수를 참고해주세요!)

 

4.1과 연결된 정점 중 주어진 시간 이하인 것을 찾음

 

(findEnableDelivery 함수를 참고해주세요!)

---

플로이드 와샬 풀이

 

1.모든 거리를 저장할 이차원 배열을 만들어줌.

 

(allDistances 변수를 참고해주세요!)

 

2. road에 있는 정보를 allDistances에 넣어줌

 

(setConnections 함수를 참고해주세요!)

 

3.floyd warshall로 각 정점에서 가장 짧은 거리를 찾음

 

(floyd 함수를 참고해주세요!)

 

4.1과 연결된 정점 중 주어진 시간 이하인 것을 찾음

 

(findEnableDelivery 함수를 참고해주세요!)

---

Source Code

 

다익스트라 풀이

 

 

플로이드 와샬 풀이