[Swift 알고리즘] 프로그래머스 - 배달

안녕하세요 코코종입니다.

이문제는 처음에 dp로 구현했지만 40.6점만 받을수 있었습니다 ㅜㅜ 뭔가 맞는거 같은뎁... 모르겠어서 다른분들의 풀이를 참고했습니다...

import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    // 1번에서 시작함!
    
    // road 내에서 [Int]: [a,b,c] -> a에서 b까지 가느데 c가 걸린다.
    // dp로 해서 1번 마을에서 이어진 애들부터 해서 가면서 최단 시간을 구하자!
    // 최단 거리를 나타낸 dp
    var dp: [Int] = Array(repeating: 50*10000, count: N+1) // index 0 미사용
    // lines i와 연결된 마을들의 배열
    var lines: [[(Int, Int)]] = Array(repeating: [], count: N+1)
    
    // 1인 경우 처리
    if N == 1 {
        return 1
    }
    
    dp[1] = 0 // 1마을에서는 0의 거리
    
    for r in road {
        lines[r[0]].append((r[1], r[2]))
        lines[r[1]].append((r[0], r[2]))
    }
    
    for i in 1...N { // 2마을 부터 시작!
        for line in lines[i] { // line: [(Int, Int)] - i와 이어진 모임 (to, dis)
            let to = line.0
            let dis = line.1
            // print("i, to, dis", i, to, dis)
            dp[to] = min(dp[i] + dis, dp[to])
        }
    }

    // print(dp)
    answer = dp.filter { $0 <= k }.count

    return answer
}

검색을 해보니 다익스트라 알고리즘으로 풀어야 하더라구요! (근데 비슷하게 한거아닌가? 싶긴하지만...암튼.. 까라면 까야쥐...)

플로이드 와샬 알고리즘으로도 풀 수 있다고 합니다! 근데 다 까먹어서 복습하느라 시간이 좀 걸렸습니다.

 

저는 다른분들의 풀이를 참고해서 다익스트라 알고리즘으로 풀었는데요. 문제에서는 1번 마을에서 출발하는게 고정이기 때문입니다! 

import Foundation

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    // 1번에서 시작함!
    
    // road 내에서 [Int]: [a,b,c] -> a에서 b까지 가느데 c가 걸린다.
    // dp로 해서 1번 마을에서 이어진 애들부터 해서 가면서 최단 시간을 구하자!
    // 최단 거리를 나타낸 dp
    var dp: [Int] = Array(repeating: 50*10000, count: N+1) // index 0 미사용
    // lines i와 연결된 마을들의 배열
    let maxV = 50 * 100000
    var graph: [[Int]] = Array(repeating: Array(repeating: maxV, count: N+1), count: N+1)
    
    // 1인 경우 처리
    if N == 1 {
        return 1
    }
    
    dp[1] = 0 // 자기자신
    
    for r in road {
        let start = r[0]
        let end = r[1]
        let dis = r[2]
        // 직접 연결된 것중 가장 작은거로 초기화(a,b를 연결하는 도로가 여러개가 있을 수 있어서 가장 짧은걸 택함)
        graph[start][end] = min(graph[start][end], dis)
        graph[end][start] = min(graph[end][start], dis)
    }
    // print(graph)
    
    var queue: [(Int, Int)] = [(1,0)] // 마을, 거리 - 자기자신꺼 먼저 넣음
    var index = 0 // 직접 삭제하면 오래걸려서 index를 이동
    
    while index < queue.count {
        let q = queue[index] // 가장 앞에꺼(처럼 쓰이는 것)
        index += 1 // 다음 칸으로 이동
        
        for i in 1...N { // 범위 주의!! 1..<N 이아님!! (0 index 미사용!)
            if graph[q.0][i] != maxV { // 연결된게 있을 때만!
                
                let dis = graph[q.0][i] + q.1
                if dis < dp[i] { // 최소거리여야함
                    dp[i] = dis // dp 갱신
                    queue.append((i, dis)) // queue에 추가
                }
            }
        }
        
    }
    
    answer = dp.filter{ $0 <= k }.count
    return answer
}

주석으로 설명을 거의 다 달아둬서 어려움은 없을거라고 생각합니다!

1에서부터 방문 가능한 마을과 그 거리를 queue에 넣어주고, Swift에서는 queue가 구현되어 있지 않으니 index를 이용해서 야매로 구현했구요. 연결된게 있다면 최소 거리(dp)를 갱신해주면서 queue에 해당 정보 (목적지 마을, 거리)를 추가해줍니다.

 

여담으로 카카오의 '합승 택시 요금'문제와 비슷하네요! 얘는 플로이드 와샬 알고리즘을 써야한다고 기억합니다