[프로그래머스] 합승 택시 요금 with Swift

• 2021 KAKAO BLIND RECRUITMENT
• 합승 택시 요금
• Level 2

 

문제

• 두 사람이 시작지점 S 로 부터 각자의 목적지 A, B에 도착할 때까지 택시 비용을 최소로 하려고 함
• 각 간선의 표시는 해당 도로를 사용하는데 드는 비용이며, 두 사람이 특정 위치까지 합승하여 비용을 절감할 수 있음

 

• 지점은 1에서 n개. n은 3이상 200이하
• 지점 s, a, b 는 1이상 n이하 자연수이며, 서로 다른 값
• fares 는 [c, d, f] 로 이루어진 배열이며, c와 d 사이 요금이 f 라는 뜻
• 동일한 구간에 대한 요금 정보는 1번만 주어짐
• f 는 1이상 100,000이하

 

Idea

• 시작 지점에서 모든 지점까지 최단 거리 구하기
• 모든 지점에서 A 까지, 모든 지점에서 B까지의 최단 거리 구하기
• 즉, S → 모든 지점, A → 모든 지점, B → 모든 지점 까지의 최단 거리 구하기

 

• 그다음 시작 지점 ~ 특정 노드 + 특정 노드 ~ A + 특정 노드 ~ B 비용을 합하여 가장 적은 비용이 드는 경우를 찾으면 됨

 

Code

Swift

• 다익스크라 알고리즘으로 구현

► 다익스트라 알고리즘 with Swift

다익스트라 알고리즘 with Swift

• 정확도 및 효율성 모두 통과!
• 세 값을 더하는 과정에서 세 값 중 Int.max가 있는 경우에 core dump 에러가 발생하므로 예외처리가 필요함

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    
    var graph = Array(repeating: [(Int, Int)](), count: n+1)
    for fare in fares {
        graph[fare[0]].append((fare[1], fare[2]))
        graph[fare[1]].append((fare[0], fare[2]))
    }
    
    func dijkstra(start: Int) -> [Int] {
        
        var costs = Array(repeating: Int.max, count: n+1)
        var node_set = Array(repeating: false, count: n+1)
        
        costs[start] = 0
        var queue = [(start, 0)]
        
        while !queue.isEmpty {
            queue.sort { $0.1 < $1.1 }
            let (node, cost) = queue.removeFirst()
            node_set[node] = true
            
            for (next, fee) in graph[node] {
                if !node_set[next], cost + fee < costs[next] {
                    costs[next] = cost + fee
                    queue.append((next, cost + fee))
                }
            }
        }
        
        return costs
    }
    
    let costS = dijkstra(start: s)
    let costA = dijkstra(start: a)
    let costB = dijkstra(start: b)
    
    var answer = Int.max
    for node in 1...n {
        if costS[node] != Int.max, costA[node] != Int.max, costB[node] != Int.max {
            let totalFare = costS[node] + costA[node] + costB[node]
            answer = min(answer, totalFare)
        }
    }
    
    return answer
}