Dijkstra(최단거리)_programmers_SW2018 배달 [swift]

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

 

접근 방법

1. 1번 마을에서 2...N번 마을까지, 갈 수 있는지 여부를 재귀를 사용하여 확인한다. -> 1차 코드
   • 반복적으로 탐색하는 경로가 생기므로 효율이 떨어짐을 인식.
2. 1번 마을에서 k 이하까지, 탐색 가능한 모든 경로를 탐색하여, 방문한 마을을 기록한다. -> 2차 코드.
   • 아무리 용을써도 해결 할 수 없는 반례가 있었다....
3. Dijkstra 알고리즘 사용... 아래는 코드의 실행순서에 따른 설명이다.
   
   1. 매개변수 road를 사용하여 2차원 배열 map을 그린다. 이 떄, i행, j열의 원소 : i번 마을에서 j번 마을로 이동시간. 간선이 없는 경우는 -1로 둔다.
   2. 1번 마을에서 출발한다. var distance는 1번마을에서 각 마을로 이동하는데 걸리는 최단 시간이다.
   3. 각 마을로의 접근 시간은 아직 알 수 없으므로, -1로 초기화 한 뒤, distance[0]은 1번 마을에서 1번 마을로 이동이므로, 0이다.
   4. var queue는 우선순위 queue이다. queue의 원소는 (n번 마을, 걸리는 시간) 1번 마을로부터 시작하므로, queue.append( (0,0 ) )
   5. 반복문은 queue의 원소가 존재하는 동안, queue는 우선순위 queue이므로,  걸리는 시간 기준으로 sort한다.
   6. queue의 첫번째 원소를 꺼내어, 해당 원소에 도달하는데, 필요한 시간( input.1 )과 기록된 최단 시간( dintance[input.0] )을 비교하여, 최단 시간이 더 빠르다면, 다음 원소를 꺼내고, 최단 시간이 같거나 느릴 경우, dajikstra(:)를 실행한다.
   7. map[start]는 start마을에서 각 마을까지의 이동 시간이다. 이 때, index == start는 n마을에서 n마을로 즉, 같은 마을로 이동하는 경우이므로 continue, length <0인 경우는, 마을간의 이동경로가 없는 경우이다.
   8. distance[index] < 0 인 경우는, 1번 마을에서 index마을까지의 최단 시간이 기재되지 않은 경우이다. 그러므로, 1번 마을에서 start마을 까지의 거리 + start마을에서 index 마을까지의 거리로 할당한다. > distance[index] = distance[start] + length
   9. distance[index] > distance[start] + length 일 경우, index마을까지의 최단거리 보다, distance[start] + length가  작거나 같으므로, 최단 거리 distance를 갱신하고, index 마을과 연결된 마을의 최단 거리를 확인 하기 위해, queue에 갱신된 정보를 추가한다.

 

정답 코드

class programmers_2018SWCoding_배달 {
    
    var map = [[Int]]()
    var distance = [Int]()
    var queue = [(Int, Int)]()
    
    func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {

        makeMap(size: N, road: road)
        distance = .init(repeating: -1, count: N)
        distance[0] = 0
        
        queue.append((0, 0))
        while !queue.isEmpty {

            queue.sort(by: {
                $0.1 < $1.1
            })
            
            let input = queue.removeFirst()
            
            if distance[input.0] < input.1 {
                continue
            }

            dijkstra(start: input.0)
        }
        return distance.filter({
            $0 <= k
        }).count
    }
    
    func makeMap(size: Int, road: [[Int]]) {
        var tempMap = [[Int]].init(repeating: [Int].init(repeating: -1,
                                                         count: size),
                                   count: size)
        
        for info in road {
            let targetValue = tempMap[info[0]-1][info[1]-1]
            
            if targetValue > info[2] || targetValue < 0 {
                tempMap[info[0]-1][info[1]-1] = info[2]
                tempMap[info[1]-1][info[0]-1] = info[2]
            }
            
        }
        
        map = tempMap
        
        for i in 0..<size {
            map[i][i] = 0
        }
    }
    
    func dijkstra(start: Int) {
        for (index,length) in map[start].enumerated() {
            if index == start {
                continue
            }
            
            if length < 0 {
                continue
            }
            
            if  distance[index] < 0 || distance[index] > distance[start] + length {
                
                distance[index] = distance[start] + length
                queue.append((index, length + distance[start]))
            }
            
        }
        
    }
    
}

 

1차 코드

시간 초과

 

각 목적지에 대해 k시간 이하로 접근 가능한지 확인을 재귀를 사용하여 확인한다.

정확성 테스트

테스트 1 〉	통과 (0.37ms, 16.2MB)
테스트 2 〉	통과 (0.12ms, 16.6MB)
테스트 3 〉	통과 (0.20ms, 16.6MB)
테스트 4 〉	통과 (0.17ms, 16.5MB)
테스트 5 〉	통과 (0.34ms, 16.6MB)
테스트 6 〉	통과 (0.17ms, 16.3MB)
테스트 7 〉	통과 (0.24ms, 16.3MB)
테스트 8 〉	통과 (0.18ms, 16.3MB)
테스트 9 〉	통과 (0.09ms, 16.4MB)
테스트 10 〉	통과 (0.37ms, 16.6MB)
테스트 11 〉	통과 (0.39ms, 16.5MB)
테스트 12 〉	통과 (9892.42ms, 16.6MB)
테스트 13 〉	통과 (838.71ms, 16.6MB)
테스트 14 〉	통과 (111.23ms, 16.8MB)
테스트 15 〉	통과 (1698.04ms, 17MB)
테스트 16 〉	통과 (896.62ms, 16.6MB)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	통과 (313.59ms, 16.4MB)
테스트 19 〉	통과 (225.69ms, 16.9MB)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	통과 (812.57ms, 17.1MB)
테스트 22 〉	통과 (3862.06ms, 16.7MB)
테스트 23 〉	실패 (시간 초과)
테스트 24 〉	실패 (시간 초과)
테스트 25 〉	실패 (시간 초과)
테스트 26 〉	통과 (1031.06ms, 17.2MB)
테스트 27 〉	실패 (시간 초과)
테스트 28 〉	실패 (시간 초과)
테스트 29 〉	실패 (시간 초과)
테스트 30 〉	통과 (418.19ms, 17.2MB)
테스트 31 〉	실패 (시간 초과)
테스트 32 〉	실패 (시간 초과)

채점 결과

정확성: 68.8

합계: 68.8 / 100.0

class programmers_2018SWCoding_배달 {
    
    struct RoadInfo {
        let lhs : Int
        let rhs : Int
        let length : Int
        
        func other(_ with: Int) -> Int {
            if with == lhs {
                return rhs
            }
            
            return lhs
        }
    }
    
    var infos = [RoadInfo]()
    
    func transform2Info(_ road: [[Int]]) -> [RoadInfo] {
        var sol = [RoadInfo]()
        
        for info in road {
            let tmp = RoadInfo.init(lhs: info[0], rhs: info[1], length: info[2])
            sol.append(tmp)
        }
        
        return sol
    }
    
    func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
        var answer = 0

        infos = transform2Info(road)
        
        for n in 1...N {
            if true == recursion(destination: n, nowPosition: 1, limit: k, movedLength: 0) {
                print(n)
                answer += 1
            }
        }
        

        return answer
    }
    
    func recursion(destination: Int, nowPosition: Int, limit: Int, movedLength: Int) -> Bool {
        if movedLength > limit {
            return false
        }
        
        if destination == nowPosition {
            return true
        }
        
        let nextList = infos.filter({ info in
            info.lhs == nowPosition || info.rhs == nowPosition
            
        })
        
        for next in nextList {
//            print(destination, nowPosition, limit, movedLength, next.other(nowPosition), next.length)
            if true == recursion(destination: destination, nowPosition: next.other(nowPosition), limit: limit, movedLength: movedLength + next.length) {
                return true
            }
        }
        
        return false
    }
    
    
    /*
     N    road    K    result
     5    [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]    3    4
     6    [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]    4    4
     
     */
}

 

 

2차 코드

처음부터 끝까지 가면서 방문한 곳을 기록한다.

recursion마다 history를 사용하여, 방문한 곳을 다시 방문하는 경우를 제외할 수 있으며, 서로 다른 경우를 탐색 할 수 있다.

 

하나의 테스트가 timeout.

처음부터 끝까지 탐색하는데 오랜 시간이 걸리는 경우가 반례인 것으로 추정

정확성 테스트

테스트 1 〉	통과 (0.36ms, 16.4MB)
테스트 2 〉	통과 (0.43ms, 16.4MB)
테스트 3 〉	통과 (0.69ms, 16.5MB)
테스트 4 〉	통과 (0.18ms, 16.4MB)
테스트 5 〉	통과 (0.10ms, 16.5MB)
테스트 6 〉	통과 (0.15ms, 16.6MB)
테스트 7 〉	통과 (0.16ms, 16.2MB)
테스트 8 〉	통과 (0.10ms, 16.5MB)
테스트 9 〉	통과 (0.11ms, 16.5MB)
테스트 10 〉	통과 (0.17ms, 16.1MB)
테스트 11 〉	통과 (0.20ms, 16.5MB)
테스트 12 〉	통과 (0.39ms, 16.4MB)
테스트 13 〉	통과 (0.41ms, 16.3MB)
테스트 14 〉	통과 (4.98ms, 16.6MB)
테스트 15 〉	통과 (37.42ms, 16.7MB)
테스트 16 〉	통과 (0.25ms, 16.4MB)
테스트 17 〉	통과 (0.21ms, 16.6MB)
테스트 18 〉	통과 (0.80ms, 16.6MB)
테스트 19 〉	통과 (1.97ms, 17MB)
테스트 20 〉	통과 (2.05ms, 16.6MB)
테스트 21 〉	통과 (6.97ms, 16.8MB)
테스트 22 〉	통과 (3.66ms, 16.5MB)
테스트 23 〉	통과 (26.35ms, 16.8MB)
테스트 24 〉	통과 (118.54ms, 16.6MB)
테스트 25 〉	통과 (7.93ms, 16.9MB)
테스트 26 〉	통과 (14.57ms, 17.1MB)
테스트 27 〉	통과 (36.18ms, 17.2MB)
테스트 28 〉	통과 (23.01ms, 16.8MB)
테스트 29 〉	통과 (109.60ms, 17.1MB)
테스트 30 〉	통과 (21.67ms, 17.2MB)
테스트 31 〉	통과 (0.55ms, 16.6MB)
테스트 32 〉	실패 (시간 초과)

채점 결과

정확성: 96.9

합계: 96.9 / 100.0

    struct RoadInfo {
        let lhs : Int
        let rhs : Int
        let length : Int
        
        func other(_ with: Int) -> Int {
            if with == lhs {
                return rhs
            }
            
            return lhs
        }
    }
    
    var infos = [RoadInfo]()
    
    func transform2Info(_ road: [[Int]]) -> [RoadInfo] {
        var sol = [RoadInfo]()
        
        for info in road {
            let tmp = RoadInfo.init(lhs: info[0], rhs: info[1], length: info[2])
            sol.append(tmp)
        }
        
        return sol
    }
    
    func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
        var answer = 0

        infos = transform2Info(road)
        
        recursion(nowPosition: 1, limit: k, movedLength: 0, boundary: N)
        
        return visited.count
    }
    
    var visited = Set<Int>()
    
    func recursion(nowPosition: Int, limit: Int, movedLength: Int, boundary: Int, history: Set<Int> = []) {
        
        if movedLength > limit {
            visited = visited.union(history)
            return
        }
        
        var newHistory = history
        if !newHistory.insert(nowPosition).inserted {
            visited = visited.union(history)
            return
        }
        
//        let newBoundary = Set<Int>.init(1...boundary).subtracting(newHistory)
        
        let nextList = infos.filter({ info in
            info.lhs == nowPosition || info.rhs == nowPosition
        })
//        .filter({ info in
//            !(newHistory.contains(info.lhs) && newHistory.contains(info.rhs))
//        })
//        .filter({ info in
//            newBoundary.contains(info.rhs) || newBoundary.contains(info.lhs)
//        })
        
        for next in nextList {
            recursion(nowPosition: next.other(nowPosition),
                                 limit: limit,
                                 movedLength: movedLength + next.length,
                                 boundary: boundary,
                                 history: newHistory)
        }
    }