[프로그래머스] 배달 Swift

프로그래머스 - 배달

나의 풀이

• 합승 택시 요금문제를 풀면서 사용했던 “Floyd-Warshal 알고리즘”을 활용했다.
• 자기 자신을 0으로 꼭 초기화 하자 .. !

import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    
    var coastArr: [[Int]] = []
    var arr: [Int] = []
    
    // 초기화
    for _ in 0...N{
        arr.append(999999999)
    }
    
    for i in 0...N{
        coastArr.append(arr)
        coastArr[i][i] = 0 // 자기 자신은 0으로 초기화
    }
    
    // coastArr 정의
    for i in 0..<road.count{
    	// road가 두 개 이상일 경우 최솟값으로 pick
        if coastArr[road[i][0]][road[i][1]] > road[i][2]{
            coastArr[road[i][0]][road[i][1]] = road[i][2]
            coastArr[road[i][1]][road[i][0]] = road[i][2]
        }
    }
    for k in 1...N{
        for i in 1...N{
            for j in 1...N{
                if coastArr[i][k] + coastArr[k][j] < coastArr[i][j]{
                    coastArr[i][j] = coastArr[i][k] + coastArr[k][j]
                }
            }
        }
    }
    
    for i in 1...N{
        if coastArr[1][i] <= k{
            answer += 1
        }
    }

    return answer
}