다익스트라 알고리즘

시작점을 주고 나머지 정점들과 시작점 과의 최단거리 구하기.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.
2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

처음 시작은 자기자신과의 거리를 0으로 두고

시작점과 나머지 정점들의 거리를 무한으로 초기화 한다.

⇒ dist[] 배열 거리를 나타낸다.

그래프 정점간의 거리

⇒ d[i][j] 정점간 거리를 나타낸다.

0번을 통해 k번 정점으로 가는 거리 dist[0] + d[0][k]이고,

이게 만약 dist[k] 보다 작다면 dist[k]가 갱신된다.

만약 노드간 거리 값으로 음수가 있다면?

벨만 포드 알고리즘 사용해야 한다.

import Foundation

func solution(_ N:Int, _ roads:[[Int]], _ k:Int) -> Int {
    var answer = 0
    var graph : [Int: [[Int]]] = [:]
    var dist = Array(repeating: Int.max, count: N + 1)
    var visited = Array(repeating: false, count: N + 1)
    dist[1] = 0
    for road in roads {
        var temp1 = graph[road[0]] != nil ? graph[road[0]]! : [[Int]]()
        temp1.append([road[1], road[2]])
        
        var temp2 = graph[road[1]] != nil ? graph[road[1]]! : [[Int]]()
        temp2.append([road[0], road[2]])
        
        graph[road[0]] = temp1
        graph[road[1]] = temp2
    }
    var pq : [Int] = [1]
    while !pq.isEmpty {
        pq.sort {
            dist[$0] <= dist[$1]
        }
        let top = pq.removeFirst()
        visited[top] = true
        for next in graph[top]! {
            if !visited[next[0]] {
                if dist[top] + next[1] < dist[next[0]] {
                     dist[next[0]] = dist[top] + next[1]
                     pq.append(next[0])
                }
            }
        }
    }

    return dist.filter { $0 <= k}.count 
}