글 읽기 - 11725 시간초과 이유..

glorylk 2년 전 0

dfs로 풀었는데 왜 시간초과일까요..?

let n = Int(readLine()!)!
var graph:[Int:[Int]] = [Int:[Int]]()
for i in 0..<n-1{
    let given = readLine()!.split(separator: " ").map{Int($0)!}
    if graph[given[0]] == nil { graph[given[0]] = []}
    if graph[given[1]] == nil { graph[given[1]] = []}
    graph[given[0]]?.append(given[1])
    graph[given[1]]?.append(given[0])
}

var parent = Int()
var result: [Int] = Array(repeating: 0, count: n+1)
func DFS(graph:[Int:[Int]], start:Int) -> [Int]{
    var visitedQueue : [Int] = []
    var needVisitStack : [Int] = [start]
    while(!needVisitStack.isEmpty){
        let node = needVisitStack.removeLast()
        parent = node
        if !visitedQueue.contains(node){
            visitedQueue.append(node)
            let child = graph[node] ?? []
            needVisitStack += graph[node] ?? []
            for i in child where i != result[node]{
                result[i] = node
            }
        }
    }
    return visitedQueue
}
DFS(graph: graph, start: 1)
result[2...n].forEach{
    print($0)
}

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

문제

문제

출처

ICPC

11725 시간초과 이유..

glorylk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말