[카카오 기출] Swift - 합승 택시 요금

합승 택시 요금

• 다익스트라

🍎 지문 해석

• 무지는 택시비를 아끼고 싶다.
• 어피치와 택시를 같이 타고 일정 지점까지 같이 가고 거기서 따로 택시를 타고 집에 갔을 때와 처음부터 각자 따로 갔을 때를 비교해서 더 적은 금액이 무엇인지 구하면 된다.
• V = 200
• E = (200 * 199) / 2
• 시간복잡도 Elog(V) -> 200log200
  • 하나의 정점에서 다른 모든 정점까지 최소 요금을 구하는 경우 -> 200log200

🍎 문제 접근

• 음의 가중치가 없는 간선에서 최단거리 -> 최소힙 기반의 우선순위 큐를 통한 다익스트라 알고리즘
• 두가지를 구해야 한다.
  • 시작 지점 S에서 A와 B까지 각자 택시를 타고 갔을때,
    • S -> A, S -> B
    • 이 부분은 S에서 모든 정점까지의 최소 요금을 구한 후 이미 구해진 해당 지점들(A, B)까지 최소 요금을 구하면 된다.
      • fromStoAll[A], fromStoAll[B]
    • 구해진 값을 더해주면 시작점 부터 따로 택시를 타고 집에 갔을때의 택시 요금이 구해진다
    • let abSeparate = fromStoAll[a] + fromStoAll[b]
  • 어느 지점까지는 같이 가다가 해당 지점에서 따로 집에가는 경우
    • 이 부분이 어려웠다. 처음에는 시작점에서 A와 B로 가는 경우를 더하고 거기서 같이 택시를 타고 간 부분을 빼주려고 했는데, 어느 지점까지 같이 택시를 타고 갔는지 알 방법이 없었다. 대략 아래와 같은 로직
    • (fromStoAll[a] + fromStoAll[b]) - (같이 택시를 탄 부분의 요금)
    • 같이 택시를 탄 부분의 요금을 구하는 방법은 다익스트라의 특징을 파악하면 구할 수 있었다.
    • 만약 무지와 어피치가 i라는 정점까지 같이 택시를 타고 갔다고 해보자. 그럼 다익스트라 알고리즘의 특징을 이용해 아래와 같은 로직을 만들 수 있다.
      • S부터 i까지 + i부터 A까지 + i부터 B까지.
    • 위의 코드는 내가 처음에 생각했던 두 요금을 더하고 중복되는것을 빼주는 로직 대신 아예 처음부터 시작점에서 i까지 요금을 구하는 방법으로 딱 한번만 계산한다! 이후 정점 i에서 A와 B까지의 최소 택시 요금을 계산하면 "일정 부분까지 같이 택시를 타고 갔다가 그 부분에서 각자 따로 집에가는 로직"을 만들 수 있다.
• i에서 부터 다른 모든 정점까지의 최소 요금을 구하는 함수 구현
  • 매개변수로 X를 넣어주면 X부터 다른 모든 정점까지의 최소 요금을 구해주는 함수를 만들었다.
  • 이 함수를 이용해서 시작점이 아닌 모든 정점(i)을 하나씩 넣어가면서 i부터 다른 모든 정점까지의 최소 요금을 구할 수 있다.

🍎 문제 풀이 및 전체 코드

import Foundation

var N = 0
public struct Heap<T> {
    var nodes: [T] = []
    let comparer: (T,T) -> Bool

    var isEmpty: Bool {
        return nodes.isEmpty
    }

    init(comparer: @escaping (T,T) -> Bool) {
        self.comparer = comparer
    }

    func peek() -> T? {
        return nodes.first
    }

    mutating func insert(_ element: T) {
        var index = nodes.count

        nodes.append(element)

        while index > 0, comparer(nodes[index], nodes[(index-1)/2]) {
            nodes.swapAt(index, (index-1)/2)
            index = (index-1)/2
        }
    }

    mutating func delete() -> T? {
        guard !nodes.isEmpty else {
            return nil
        }

        if nodes.count == 1 {
            return nodes.removeFirst()
        }

        let result = nodes.first
        nodes.swapAt(0, nodes.count-1)
        _ = nodes.popLast()

        var index = 0

        while index < nodes.count {
            let left = index * 2 + 1
            let right = left + 1

            if right < nodes.count {
                if comparer(nodes[right], nodes[left]),
                   comparer(nodes[right], nodes[index]) {
                    nodes.swapAt(right, index)
                    index = right
                } else if comparer(nodes[left], nodes[index]){
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else if left < nodes.count {
                if comparer(nodes[left], nodes[index]) {
                    nodes.swapAt(left, index)
                    index = left
                } else {
                    break
                }
            } else {
                break
            }
        }
        return result
    }
}

extension Heap where T: Comparable {
    init() {
        self.init(comparer: <) // min heap
        // self.init(comparer: >)  max heap
    }
}

struct EdgeNode: Comparable {
    var node: Int
    var cost: Int

    static func < (_ lhs: EdgeNode, _ rhs: EdgeNode) -> Bool {
        return lhs.cost < rhs.cost
    }
}

func Dijkstra(_ start: Int, _ connectionInfo: inout [[(Int, Int)]]) -> [Int] {
    var costArr = [Int](repeating: 1000000, count: N + 1)
    costArr[start] = 0

    var pq = Heap<EdgeNode>()
    pq.insert(EdgeNode(node: start, cost: 0))

    while !pq.isEmpty {
        let current = pq.delete()!

        if costArr[current.node] < current.cost { continue }

        for info in connectionInfo[current.node] {
            let nextNode = info.0
            let costToNextNode = info.1
            let tempCost = current.cost + costToNextNode

            if tempCost < costArr[nextNode] {
                costArr[nextNode] = tempCost
                pq.insert(EdgeNode(node: nextNode, cost: tempCost))
            }
        }
    }
    return costArr
}

func solution(_ n: Int, _ s: Int, _ a: Int, _ b: Int, _ fares: [[Int]]) -> Int {
    N = n
    //MARK: 양방향 간선이므로 X -> Y , Y -> X 비용 저장
    var connectionInfo = [[(Int, Int)]](repeating: [(Int, Int)](), count: N + 1)
    for fareInfo in fares {
        let from = fareInfo[0]
        let to = fareInfo[1]
        let cost = fareInfo[2]
        connectionInfo[from].append((to, cost))
        connectionInfo[to].append((from, cost))
    }
    let fromStoAll = Dijkstra(s, &connectionInfo)
    let abSeparate = fromStoAll[a] + fromStoAll[b] 
    var result = abSeparate

    //MARK: 시작점이 아닌 모든 정점(i)을 순회하면서 
    // - "i 까지 같이 택시를 타고 이후엔 각자 택시를 탔을 때의 비용"과 "처음부터 각자 택시를 탔을 때의 비용"을 비교
    // - 더 작은 값이 문제의 답.
    for i in 1...N {
        if s != i {
            let fromItoAll = Dijkstra(i, &connectionInfo)
            result = min(result, fromStoAll[i] + fromItoAll[a] + fromItoAll[b])
        }
    }
    return result
}