dijkstra_Programmers_배달 [swift]

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

분명히 풀었던 문제지만, 그냥 복습차 다시풀어봤다.

예전에는 이해를 반만하고 풀었던 것 같지만 나아진 기분

 

import Foundation
    
func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    // index + 1 == 마을 번호
    var distance = [Int](repeating: Int.max, count: N+1)
    // 출발 : (도착, 거리)
    var graph = [Int: [(Int, Int)]]()
    // (도착, 거리)
    var queue = [(Int, Int)]()
    
    for info in road {
        let start = info[0]
        let end = info[1]
        let dist = info[2]
        graph[start, default: []].append((end, dist))
        graph[end, default: []].append((start, dist))
    }
    
    distance[1] = 0
    queue.append((1,0))
    
    while !queue.isEmpty {
        let (start, moved) = queue.removeFirst()
        
        let nexts = graph[start, default: []]
        for (end, move) in nexts {
            let nextMove = moved + move
            if distance[end] > nextMove {
                distance[end] = nextMove
                queue.append((end,nextMove))
                queue.sort(by: { (lhs, rhs) in
                    lhs.1 < rhs.1
                })
            }
        }
    }
    
    return distance.filter({ $0 <= k }).count
    
}