글 읽기 - 이런식의 bfs는 시간복잡도 분석은 어떻게 해야할까요?

iyeaaa 1년 전 0

시간초과가 뜨는데 이런식의 bfs는 시간복잡도 분석을 어떻게 해서 시간초과가 뜰지 안뜰지 분석하는게 너무 어려운것 같습니다.

typealias Class = (S: Int, T: Int)
let N = io.readInt()
var classes: [Class] = crtClasses()
var visit = [Bool](repeating: false, count: N)
var count = 1

var queue = [0], index = 0; visit[0] = true
while index < queue.count {
    let cur = queue[index]; index += 1
    for i in stride(from: cur+1, to: N, by: 1) {
        if visit[i] { continue }
        visit[i] = true
        if classes[cur].T > classes[i].S {
            queue.append(i)
            count += 1
        } else {
            queue.append(i)
            break
        }
    }
}

print(count)



func crtClasses() -> [Class] {
    var result = [Class]()
    for _ in 0..<N {
        result.append(Class(S: io.readInt(), T: io.readInt()))
    }
    return result.sorted{$0.S < $1.S}
}

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

문제

문제

출처

ICPC

이런식의 bfs는 시간복잡도 분석은 어떻게 해야할까요?

iyeaaa 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말