[프로그래머스] 배달 with Swift

• Summer/Winter Coding(~2018)
• 배달
• Level 2

 

문제

• N 개의 마을로 이루어짐
• 각 마을은 양방향 통행 가능한 도로로 연결되어 있고
• 각 도로 별로 걸리는 시간이 다름
• 1번 마을에서 배달 하려고 하는데 K 시간 이하로 배달이 가능한 마을만 주문을 받음

 

• N은 1이상 50이하
• road 길이(도로 정보 개수)는 1이상 2,000이하
• road 는 길이가 3인 배열 (a, b, c)
• a, b (1이상 N이하, a != b) : 마을 번호, c (1이상 10,000이하 자연수) : 걸리는 시간
• a, b를 연결하는 도로는 여러 개가 있을 수 있음
• K 는 음식 배달이 가능한 시간. 1이상 500,000이하
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 반환

 

Idea

• 주어진 정보를 토대로 그래프를 그린 다음
• 최단 경로(다익스트라) 알고리즘을 이용해서 1번 마을로 부터 특정 노드까지의 최단 거리를 구하기
• k 이하의 값만 가진 노드의 개수를 반환하면 됨

 

Code

Swift

1. 다익스트라로 알고리즘으로 구현

► 다익스트라 알고리즘 with Swift

다익스트라 알고리즘 with Swift

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {

    if N == 1 { return 1 }
    
    // 1. 그래프 그리기
    var graph = Array(repeating: [(Int, Int)](), count: N+1)
    for info in road {
        graph[info[0]].append((info[1], info[2]))
        graph[info[1]].append((info[0], info[2]))
    }
    
    // 2. 시작 위치로부터 각 노드까지의 최단 거리를 나타내는 배열
    var costs = Array(repeating: Int.max, count: N+1)
    
    func dijkstra(start: Int) {
        
        // 3. 시작 위치는 0으로 초기화
        costs[start] = 0
        // 4. 집합 S 에 속하는지 여부를 나타내는 배열 (S 집합이 의미하는 것 : 최단거리 계산이 끝났다는 의미)
        var s = Array(repeating: false, count: N+1)

        // 5. 우선순위 큐에 시작 위치 넣기
        var queue: [(Int, Int)] = [(start, 0)]
        // 6. 우선순위 큐에 노드가 있는 동안 반복
        while !queue.isEmpty {
            // 7. 원래는 우선순위 큐(힙)에서 최단거리가 가장 짧은 노드를 뽑는 것이지만, 힙을 구현해야하기 때문에 정렬로 대체
            queue.sort { $0.1 < $1.1 }
            let (town, cost) = queue.removeFirst()
            // 8. S 집합에 추가
            s[town] = true
            // 9. 뽑힌 노드에 연결되어 있는 노드들의 비용을 업데이트
            for (next, time) in graph[town] {
                // 10. S에 포함되지 않으면서, 기존 비용보다 새로 업데이트할 비용이 더 작다면
                if !s[next], cost + time < costs[next] {
                    // 11. 비용 업데이트 및 우선순위 큐에 추가
                    costs[next] = cost + time
                    queue.append((next, costs[next]))
                }
            }
        }
    }
    dijkstra(start: 1)

    // k 값 이하의 비용을 가진 노드의 개수 반환
    return costs.filter { $0 <= k }.count
}

 

2. DFS 사용

→ 하지만 마지막 테스트케이스(32번)를 통과하지 못함 — 시간 초과 발생

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {

    if N == 1 { return 1 }
    
    var graph: [[Int?]] = Array(repeating: Array(repeating: nil, count: N+1), count: N+1)
    for info in road {
        let prev = graph[info[0]][info[1]] ?? info[2]
        if info[2] <= prev {
            graph[info[0]][info[1]] = info[2]
            graph[info[1]][info[0]] = info[2]
        }
    }
    
    var visited = Array(repeating: false, count: N+1)
    var takeTimeFromTown1 = Array(repeating: Int.max, count: N+1)
    func dfs(_ s: Int, _ takeTime: Int) {
        visited[s] = true
        takeTimeFromTown1[s] = takeTimeFromTown1[s] > takeTime ? takeTime : takeTimeFromTown1[s]
        for next in 2...N {
            if let time = graph[s][next],
            takeTime + time <= k,
            !visited[next] {
                dfs(next, takeTime + time)
            }
        }
        visited[s] = false
    }
    
    dfs(1, 0)

    return takeTimeFromTown1.filter { $0 != Int.max }.count
}