[알고리즘 연습] 합승 택시 요금 (프로그래머스 lv3, 스위프트)

문제

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

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

풀이

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {    
​​​​// 일단 그래프 짜기
​​​​var graph = Array(repeating: Array(repeating: -1, count: n+1), count: n+1)

​​​​for fare in fares {
​​​​​​​​let from = fare[0]
​​​​​​​​let to = fare[1]
​​​​​​​​let distance = fare[2]

​​​​​​​​graph[from][to] = distance
​​​​​​​​graph[to][from] = distance
​​​​}

​​​​// 같이타고 간다는 것은 그만큼의 비용을 내고 S를 이동시키는 것    
​​​​// 일단 S에서 각 위치로 가는 비용을 다익스트라로 계산해놓기
​​​​var sdistance = Array(repeating: Int.max, count: n+1)
​​​​var queue = [s]
​​​​var head = 0
​​​​sdistance[s] = 0

​​​​while queue.count - head > 0 {
​​​​​​​​let now = queue[head]
​​​​​​​​head += 1

​​​​​​​​for i in 1...n {
​​​​​​​​​​​​let cost = sdistance[now] + graph[now][i]
​​​​​​​​​​​​if graph[now][i] >= 0 && sdistance[i] > cost {
​​​​​​​​​​​​​​​​sdistance[i] = cost
​​​​​​​​​​​​​​​​queue.append(i)
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​// S에서 각각의 목적지를 다익스트라로 탐색 (+ 위의 다익스트라 비용)
​​​​var minCost = Int.max
​​​​for start in 1...n {
​​​​​​​​if sdistance[start] == Int.max { continue }

​​​​​​​​var distance = Array(repeating: Int.max, count: n+1)
​​​​​​​​queue = [start]
​​​​​​​​head = 0
​​​​​​​​distance[start] = 0

​​​​​​​​while queue.count - head > 0 {
​​​​​​​​​​​​let now = queue[head]
​​​​​​​​​​​​head += 1

​​​​​​​​​​​​for i in 1...n {
​​​​​​​​​​​​​​​​let cost = distance[now] + graph[now][i]
​​​​​​​​​​​​​​​​if graph[now][i] >= 0 && distance[i] > cost {
​​​​​​​​​​​​​​​​​​​​distance[i] = cost
​​​​​​​​​​​​​​​​​​​​queue.append(i)
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​minCost = min(sdistance[start] + distance[a] + distance[b], minCost)
​​​​}

​​​​return minCost
}

• 다익스트라를 2번 사용하는 방법으로 문제를 해결했다.
• 일단 경로에 대한 그래프를 짜놓고 (경로가 없는 경우 -1로 표시)
• 먼저 중간지점까지 같이간다는 것은 각자에게 있어 출발지점을 바꾸는 것이나 마찬가지의 의미
  • 따라서 S에서 각 위치로 가는 비용을 다익스트라로 계산
• 이제 모든 노드를 기준으로 돌아가면서 다익스트라로 A,B까지 가는 거리비용을 계산
  • (A까지의 거리비용 + B까지의 거리비용 + 원래 출발지에서 현재 노드까지 오는 비용)을 계산하여 가장 적을때를 탐색