[프로그래머스][Swift] 부대복귀 - Level3

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

 

간단한 문제 요약

부대원들 여러 지역을 각각 탐색. 이 지역은 유일한 번로홀 구분됨. 한 지역에서 다른 지역으로 이동시 걸리는 시간은 1로 고정. 각 부대원들의 복귀 지점이 주어질 때 복귀할 수 있는 최단 시간을 구해라. 이때 복귀가 불가능한 인원은 -1, 바로 복귀가 가능한 인원의 최단 시간은 0이다!

문제 풀이

첫 번째 시도

Bfs로 sources별로 destination까지 매번 아래의 bfs탐색을 호출하며 각각의 부대 인원 지점에서 도착 지점까지 최단 시간을 파악하도록 구현했습니다.

 

typealias Element = (route: Int, day: Int)
func bfs(entry: Int, destination: Int, n: Int, by routes: [Int: [Int]]) -> Int {
    var queue: [Element] = [(entry, 0)]
    var queueIdx = 0
    if entry == destination { return 0 }
    var visited = Array(repeating: false, count: n)
    visited[entry-1] = true
    while queue.count > queueIdx {
        var (curPos, curDay) = queue[queueIdx]
        queueIdx += 1
        guard let directions = routes[curPos] else { continue }
        for nextPos in directions {
            let nextPosIdx = nextPos-1
            if visited[nextPosIdx] { continue }
            if nextPos == destination { return curDay + 1 }
            visited[nextPosIdx] = true
            queue.append((nextPos, curDay+1))
        }
    }
    return -1
}

 

이때 단점은 최악의 경우 bfs탐색은 100,000 개의 지역들을 탐색해야 하고, 부대원인 sources는 500명 이어서, 500 * 100,000 번의 수행연산.. 50,000,000의 연산을 해야합니다. 

 

이전에 탐색한 지역도 또 한 번 탐색하면 비효율적일 것이라는 생각이 무척 들었고 빠르게 다른 방법을 생각했습니다.

---

두 번째 시도

bfs는 본질적으로 싸이클이 없는 그래프의 노드들을 한 번씩 모두 탐색합니다. 한 노드에서 탐색하지 않은 노드들을 탐색할 때, 가까운 정점들은 동시에 탐색해 나감으로 이 문제에 적합했고, 그렇게 root node를 기준으로 모든 노드들을 탐색해나가면 어떨까 생각했습니다.

 

typealias Element = (route: Int, day: Int)
func bfs(destination: Int, n: Int, cache: inout [Int], by routes: [Int: [Int]]) {
    var queue: [Element] = [(destination, 0)]
    var queueIdx = 0
    cache[destination] = 0
    while queue.count > queueIdx {
        var (curPos, curDay) = queue[queueIdx]
        queueIdx += 1
        guard let directions = routes[curPos] else { continue }
        for nextPos in directions {
            if cache[nextPos] != -1 && cache[nextPos] <= curDay+1 { continue }
            cache[nextPos] = curDay + 1
            queue.append((nextPos, curDay+1))
        }
    }
}

 

 

destination을 root node로 해서 연관된 노드들을 bfs로 탐색해나갔고, 그때 걸리는 시간을 cache라는 객체를 통해 저장했습니다. 한번의 연산은 최악의 경우 100,000 번의 수행 연산이 발생됩니다.

 

갈 수 있는 경로들은 routes를 통해 저장했기 때문에, destination을 시작으로 갈 수 있는 모든 node의 시간들을 구해 cache에 저장한다면, 이 cache에 들어있는 각각의 값들은 최단 경로가 됩니다. 그리고 부대원들의 정보 Sources는 500개이기 때문에 O(1)의 시간복잡도로 모든 부대원들이 destination으로 가기까지 걸리는 시간은 cahce를 통해 구해나갈 수 있게됩니다.

 

코드

func solution(_ n:Int, _ roads:[[Int]], _ sources:[Int], _ destination:Int) -> [Int] {
    var routes = roads.reduce(into: [Int: [Int]]()) {
        $0[$1[0], default: []].append($1[1])
        $0[$1[1], default: []].append($1[0])
    }
    
    var cache = Array(repeating: -1, count: n+1)
    bfs(destination: destination, n: n, cache: &cache, by: routes)
    return sources.map { cache[$0] }
}

typealias Element = (route: Int, day: Int)
func bfs(destination: Int, n: Int, cache: inout [Int], by routes: [Int: [Int]]) {
    var queue: [Element] = [(destination, 0)]
    var queueIdx = 0
    cache[destination] = 0
    while queue.count > queueIdx {
        var (curPos, curDay) = queue[queueIdx]
        queueIdx += 1
        guard let directions = routes[curPos] else { continue }
        for nextPos in directions {
            if cache[nextPos] != -1 && cache[nextPos] <= curDay+1 { continue }
            cache[nextPos] = curDay + 1
            queue.append((nextPos, curDay+1))
        }
    }
}