[Level 2 / 플로이드 와샬] 배달 + Swift

문제 링크

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

문제

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

입력

let N = 6
let road = [[1, 2, 1], [1, 3, 2], [2, 3, 2], [3, 4, 3], [3, 5, 2], [3, 5, 3], [5, 6, 1]]
let k = 4

출력

4

문제 풀이

1. 배달 시간을 담을 db를 정의한다. 예를 들어, db[1][2]는 1에서 2까지의 배달 시간이다. 일단 배달이 되지 않을 (k+1)시간으로 세팅한다.
2. 배달 시간 정보가 담긴 road를 db에 적용한다. 최소 시간을 저장한다.
3. 플로이드 와샬 알고리즘에 따라 for문을 세번 돈다. i는 출발지점, k는 중간지점, j는 도착지점이다. 예를 들어, i가 1이고 k가 2이고 j가 3이라고 가정하자. 출발지인 1에서 3까지의 배달 시간이 1에서 2까지의 배달시간과 2에서 3까지의 배달시간을 합친 시간보다 크다면, 합친 시간으로 db를 수정한다.
4. db[1]에는 1에서부터 다른 배달지들까지 걸리는 시간이 담겨있다. k보다 작은 배달지들 개수를 반환한다.

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    let n = N
    var db: [[Int]] = Array(repeating: Array(repeating: k+1, count: n+1), count: n+1)
    
    for singleRoad in road {
        if db[singleRoad[0]][singleRoad[1]] > singleRoad[2] {
            db[singleRoad[0]][singleRoad[1]] = singleRoad[2]
            db[singleRoad[1]][singleRoad[0]] = singleRoad[2]
        }
    }
    
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                let time = (i == j) ? 0 : db[i][k] + db[k][j]
                if db[i][j] > time {
                    db[i][j] = time
                    db[j][i] = time
                }
            }
        }
    }
    
    return db[1].filter { $0 <= k }.count
}