글 읽기 - Swift 8% 시간초과 조언부탁드립니다

gearmamn06 5년 전 0

제가 생각한 아이디어는

우선 노드 1에서 방문할수 있는 노드들의 리스트가 있을때

이 노드들이 최초 노드 1에서 방문할 수 있는 노드임에 1로 복귀하기 이전 방문 가능한 노드라 판단하였습니다

예를들어 설명하면 1에서 방문가능한 노드가 2, 3, 4 이라고 할때, 노드 2, 3, 4를 순서대로

다익스트라를 이용하여 최단 경로를 구하는 최초 루프에서 제외합니다

가령 1로 복귀하기 바로 마지막 노드가 노드 2라고 가정을 하면 노드 1에서 2로 가는 값을 노드 2의 최단경로값에서 제외합니다.

이와같은 방법으로 2, 3, 4의 경우 각 노드의 최소값을 구하여 해당 노드에서 노드 1로 복귀하는 값을 구한 뒤

최소값을 구하여 문제를 풀려 하였습니다.

답은 잘 찾는것 같은데

8%부분에서 시간초과가 발생합니다.

다익스트라를 1에서 방문가능한 노드의 수마다 돌리기때문에 시간초과가 발생할수밖에 없는건가요?

import Foundation

//var rows = "5 6\n1 2 69 22\n1 4 44 31\n1 5 19 22\n3 5 72 88\n3 4 8 7\n1 3 9 23".split(separator: "\n")
//func readString() -> String {
//    return String(rows.removeFirst())
//}

let NM = readLine()!.split(separator: " ").map{ Int($0)! }
//let NM = readString().split(separator: " ").map{ Int($0)! }
let N = NM[0]; let M = NM[1]

let MAX = (M+1) * 10_000
let len = N + 1

var gr = [[Int]](repeating: [Int](), count: len)
var cost = [[Int]](repeating: [Int](repeating: 0, count: len), count: len)

for _ in 0..<M {
    let abcd = readLine()!.split(separator: " ").map{ Int($0)! }
//    let abcd = readString().split(separator: " ").map{ Int($0)! }
    gr[abcd[0]].append(abcd[1])
    gr[abcd[1]].append(abcd[0])
    cost[abcd[0]][abcd[1]] = abcd[2]
    cost[abcd[1]][abcd[0]] = abcd[3]
}

var checkPoints = gr[1]
var shortest = Int.max

for c in checkPoints {
    
    var q = (2...N).map{ Int($0) }
    var s = [1]
    var dst = [Int](repeating: MAX, count: len)
    dst[1] = 0
    
    var now = 1
    
    for nxt in gr[now] {
        if nxt == c { continue }
        dst[nxt] = cost[1][nxt]
    }
    
    while !q.isEmpty {
        
        var mn = Int.max; var index = 0
        for i in 0..<q.count {
            let d = dst[q[i]]
            if d < mn {
                mn = d
                index = i
            }
        }

        now = q[index]
        s.append(now)
        q.remove(at: index)
        
        
        for nxt in gr[now] {
            let d = dst[now] + cost[now][nxt]
            dst[nxt] = min(dst[nxt], d)
        }
    }

    let shrt = dst[c] + cost[c][1]
    shortest = min(shortest, shrt)
    
}

print(shortest)

gearmamn06 5년 전 0

친절하신답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.