[Swift 알고리즘] 프로그래머스(Lv.2) - 배달

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 배달" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 배달

 

---

풀이

이번 문제는 다익스트라 문제입니다. 플로이드 와샬 알고리즘으로 해결할 수 있습니다.

 

문제의 특이사항으로는 A -> B로 가는 여러 개의 경로가 존재할 수 있다는 것입니다.

따라서 문제를 자세히 읽지 않고 구현하면 실패가 나올 수 있습니다.

여러 개의 경로 중 최소 cost의 경로를 선택해야 합니다.

 

다익스트라의 정석 문제인 만큼 이 점만 주의하면 막힘 없이 해결할 수 있을 것입니다. 

 

감사합니다!

---

전체 코드

import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    
    var costs: [Int] = Array(repeating: Int.max, count: N+1)
    var graph: [[Int]] = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
    for r in road {
        graph[r[0]][r[1]] = min(r[2], graph[r[0]][r[1]])
        graph[r[1]][r[0]] = min(r[2], graph[r[1]][r[0]])
    }

    var queue: [(idx: Int, cost: Int)] = [(1, 0)]
    var index = 0    
    costs[1] = 0 //자기 자신

    while index < queue.count {
        let node = queue[index]
        index += 1
        
        for next in 1...N {
            if graph[node.idx][next] == Int.max {
                continue
            }
            
            let nCost = node.cost + graph[node.idx][next]
            if graph[node.idx][next] != Int.max && nCost < costs[next] {
                costs[next] = nCost
                queue.append((next, nCost))
            }
        }
    }
           
    answer = costs.filter { $0 <= k }.count
    return answer
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.