Dijkstra(최단거리)_programmers_가장 먼 노드

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

 

일단, 틀렸다. 듣기로는 BFS일 때, 잘 풀리는 문제라고 한다. 실제로 간선 간 거리가 1로 지정되어 있기 때문인듯.

하지만 더 풀어보지 않는 이유는 dijkstra는 제대로 구현되었다고 생각했기때문!

마지막 3개의 testCase가 dijkstra의 반례인듯.

 

코드

class programmers_다익스트라_가장먼노드 {
    
    var map : [[Int]] = .init()
    var minimumLength: [Int] = .init()

    // (node, length)
    var queue : [(Int,Int)] = .init() {
        didSet {
            queue.sort() {
                $0.1 < $1.1
            }
        }
    }

    func solution(_ n:Int, _ edge:[[Int]]) -> Int {
        setMap(n: n)
        setEdges(edges: edge)
        
        queue.append( (0,0) )
        
        while !queue.isEmpty {
            let target = queue.removeFirst()
            
            if minimumLength[target.0] < target.1 {
                continue
            }
            
            dijkstra(target: target.0)
        }
        
        return minimumLength.filter() {
            $0 == minimumLength.max()!
        }.count
    }

    func dijkstra(target: Int) {
        for (middle, ends) in map.enumerated() {
            if ends[target] < 0 {
                continue
            }
            
            if minimumLength[middle] < 0 ||
            minimumLength[middle] > minimumLength[target] + ends[target] {
                
                minimumLength[middle] = minimumLength[target] + ends[target]
                queue.append( (middle, minimumLength[middle]) )
            }
        }
        
    }

    func setEdges(edges: [[Int]]) {
        for edge in edges {
            map[edge[0]-1][edge[1]-1] = 1
            map[edge[1]-1][edge[0]-1] = 1
        }
    }

    func setMap(n: Int) {
        minimumLength = [Int].init(repeating: -1, count: n)
        minimumLength[0] = 0
        
        map = [[Int]].init(repeating: [Int].init(repeating: -1, count: n), count: n)
        
        for i in 0..<n {
            map[i][i] = 0
        }
        
    }
}

 

성적

테스트 1 〉	통과 (0.38ms, 16.3MB)
테스트 2 〉	통과 (0.31ms, 16.5MB)
테스트 3 〉	통과 (0.92ms, 16.3MB)
테스트 4 〉	통과 (5.05ms, 16.7MB)
테스트 5 〉	통과 (158.44ms, 18.5MB)
테스트 6 〉	통과 (712.43ms, 25.1MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)

채점 결과

정확성: 66.7

합계: 66.7 / 100.0

 

수정 코드와 성적

코드

import Foundation
    var dist: [Int] = .init()
    var adjList: [[(Int,Int)]] = []
    // (node, length)
    var queue : [(Int,Int)] = .init() 
// {
//         didSet {
//             queue.sort() {
//                 $0.1 < $1.1
//             }
//         }
//     }

    func solution(_ n:Int, _ edge:[[Int]]) -> Int {
        dist = .init(repeating: -1, count: n)
        dist[0] = 0
        
        adjList = .init(repeating: [], count: n)
        
        for ed in edge {
            adjList[ed[0]-1].append((ed[1]-1,1))
            adjList[ed[1]-1].append((ed[0]-1,1))
        }
        
        queue.append( (0,0) )
        
        while !queue.isEmpty {
            let target = queue.removeFirst()
            
            if dist[target.0] < target.1 {
                continue
            }
            
            dijkstra(target: target.0)
        }
        
        return dist.filter() {
            $0 == dist.max()!
        }.count
    }

    func dijkstra(target: Int) {
        for info in adjList[target] {
            
            if dist[info.0] < 0 ||
                dist[info.0] > dist[target] + info.1 {
                
                dist[info.0] = dist[target] + info.1
                queue.append((info.0, dist[info.0]))
            }
        }
        
    }

와 성적

 

dijkstra가 더 나은 성능을 보일 것으로 생각했는데, BFS의도 문제여서 그런지 어떠한 반례가 있어보인다.

혹은, 스위프트에 queue가 없어서, 우선순위 queue를 적용 할 수 없어서 일지도,,,,

정확성 테스트

테스트 1 〉	통과 (0.12ms, 16.4MB)
테스트 2 〉	통과 (0.24ms, 16.4MB)
테스트 3 〉	통과 (0.26ms, 16.6MB)
테스트 4 〉	통과 (1.50ms, 16.7MB)
테스트 5 〉	통과 (29.21ms, 16.8MB)
테스트 6 〉	통과 (97.74ms, 17.8MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)