1. 문제 설명

등산코스 정하기

2. 문제 분석

다익스트라를 통해 출발지-산봉우리까지 가는 경로 중 비용의 최댓값을 기록한다. 다익스트라를 여러 번 돌리지 않고, 출발지로부터 시작하는 시작 노드를 우선순위 큐에 모두 넣은 채로 한 번만 돌린다.

3. 나의 풀이

import sys
import heapq

def solution(n, paths, gates, summits):
    INF = sys.maxsize
    nodes = [[] for _ in range(n+1)]
    summits_set = set(summits)
    for path in paths:
        node1, node2, cost = path
        nodes[node1].append([node2, cost])
        nodes[node2].append([node1, cost])
        
    pq = []
    distances = [INF for _ in range(n+1)]
    for gate in gates:
        heapq.heappush(pq, [0, gate])
        distances[gate] = 0
    
    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if cur_cost > distances[cur_node]: continue
        
        for next_node, next_cost in nodes[cur_node]:
            total_cost = max(next_cost, cur_cost)
            if total_cost < distances[next_node]:
                distances[next_node] = total_cost
                if next_node not in summits_set:
                    heapq.heappush(pq, [total_cost, next_node])
    
    answer = [-1, INF]
    summits.sort()
    
    for summit in summits:
        if answer[1] > distances[summit]:
            answer = [summit, distances[summit]]
    return answer

import Foundation

struct PQ<T> {
    var nodes = [T]()
    let sort:(T, T) -> Bool
    
    init(sort: @escaping (T, T) -> Bool) {
        self.sort = sort
    }
    
    var isEmpty: Bool {
        return nodes.isEmpty
    }
    
    var count: Int {
        return nodes.count
    }
    
    func leftChild(from parentIndex: Int) -> Int {
        return parentIndex * 2 + 1
    }
    
    func rightChild(from parentIndex: Int) -> Int {
        return parentIndex * 2 + 2
    }
    
    func parentIndex(from child: Int) -> Int {
        return (child - 1) / 2
    }
    
    mutating func siftDown(from index: Int) {
        var parent = index
        while true {
            let left = leftChild(from: parent)
            let right = rightChild(from: parent)
            var candidate = parent
            if left < count && sort(nodes[left], nodes[candidate]) {
                candidate = left
            }
            
            if right < count && sort(nodes[right], nodes[candidate]) {
                candidate = right
            }
            
            if candidate == parent {
                return
            }
            
            nodes.swapAt(parent, candidate)
            parent = candidate
        }
    }
    
    mutating func siftUp(from index: Int) {
        var child = index
        var parent = parentIndex(from: child)
        while child > 0 && sort(nodes[child], nodes[parent]) {
            nodes.swapAt(child, parent)
            child = parent
            parent = parentIndex(from: child)
        }
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        nodes.swapAt(0, count-1)
        defer {
            siftUp(from: 0)
        }
        return nodes.removeLast()
    }
    
    mutating func push(_ element: T) {
        nodes.append(element)
        siftUp(from: count - 1)
    }
}

func solution(_ n:Int, _ paths:[[Int]], _ gates:[Int], _ summits:[Int]) -> [Int] {
    var nodes = Array(repeating: [(Int, Int)](), count: n+1)
    let summitsSet = Set(summits)
    for path in paths {
        let (node1, node2, cost) = (path[0], path[1], path[2])
        nodes[node1].append((node2, cost))
        nodes[node2].append((node1, cost))
    }
    
    func Dijkstra() -> [Int] {
        var pq = PQ<(Int, Int)>(sort: {$0.0 < $1.0})
        let INF = Int.max
        var distances = Array(repeating: INF, count: n+1)
        for gate in gates {
            pq.push((0, gate))
            distances[gate] = 0
        }
        
        while !pq.isEmpty {
            guard let curData = pq.pop() else { break }
            let curCost = curData.0
            let curNode = curData.1
            
            if distances[curNode] < curCost {
                continue
            }
            
            for nextData in nodes[curNode] {
                let nextNode = nextData.0
                let nextCost = nextData.1
                
                let totalCost = max(curCost, nextCost)
                if distances[nextNode] > totalCost {
                    distances[nextNode] = totalCost
                    if summitsSet.contains(nextNode) {
                        continue
                    }
                    pq.push((totalCost, nextNode))
                }
            }
        }
        return distances
    }
    let distances = Dijkstra()
    var answer = [Int.max, Int.max]
    for summit in summits {
        let distance = distances[summit]
        if answer[1] > distance {
            answer = [summit, distance]
        } else if answer[1] == distance {
            if answer[0] > summit {
                answer = [summit, distance]
            }
        }
    }
    return answer
}

파이썬과 동일한 로직으로 푼 스위프트 풀이. 하지만 마지막 테스트케이스인 25번에서 시간 초과를 해결하지 못했다. 커스텀 우선순위 큐를 사용해서 그런지.. 파이썬의 힙큐보다 시간 효율이 떨어진다. 어떻게 해야 풀릴까?