[알고리즘 연습] 합승 택시 요금 (프로그래머스 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까지의 거리비용 + 원래 출발지에서 현재 노드까지 오는 비용)을 계산하여 가장 적을때를 탐색