글 읽기 - 2468 swift 시간초과 이유가 궁금합니다.

glorylk 2년 전 0

dfs로 풀었는데 시간초과가 나오네요.. 이유가 궁금합니다 고수님들 알려주세요..

let n = Int(readLine()!)!
var graph : [[Int]] = [[Int]]()
var maxHeight = 0
for i in 0 ..< n {
    let givenRow = readLine()!.split(separator: " ").map{Int($0)!}
    let maxN = givenRow.max()!
    if maxHeight < maxN {
        maxHeight = maxN
    }
    graph.append(givenRow)
}
//print(graph)

var visitedQueue : [[Int]] = []


func DFS(graph:[[Int]],start:[Int],targetNumber:Int)->Bool{
    var result = Bool()
    var needVisitStack : [[Int]] = [start]
    while(!needVisitStack.isEmpty) {
        let node = needVisitStack.removeLast()
        if visitedQueue.contains(node){continue}
        else {
            if graph[node[0]][node[1]] > targetNumber {
                let movedCoordinates = availableDirection(node: node, size: n)
                needVisitStack += movedCoordinates
                result = true
            }
            visitedQueue.append(node)
        }
    }
    return result
}
func availableDirection(node:[Int],size: Int)->[[Int]]{
    let dx = [0,0,1,-1]
    let dy = [1,-1,0,0]
    let currentX = node[1]
    let currentY = node[0]
    var result = [[Int]]()
    for i in 0 ..< 4{
        let movedX = currentX + dx[i]
        let movedY = currentY + dy[i]
        if movedX >= 0 && movedX < size && movedY >= 0 && movedY < size {
            result.append([movedY,movedX])
        }
    }
    return result
}

var resultArray = [Int]()
for k in 1...maxHeight {
    visitedQueue = []
    var countN = 0
    for i in 0..<n {
        for j in 0..<n{
            if !visitedQueue.contains([i,j]) {
                if DFS(graph: graph, start: [i,j], targetNumber: k) == true {
                    countN += 1
                }
            }
        }
    }
    resultArray.append(countN)
}


print(resultArray.max()!)

wapas 2년 전 0

!visitedQueue.contains([i,j]) 에서 contains 메소드는 시간 복잡도 O(N)입니다.

그러므로 높이가 H라고 하면 위 코드는 시간 복잡도 O(N^3H) 입니다.

방문 체크를 2차원 Bool 배열로 하시면 O(N^2H)로 개선할 수 있습니다.

+ 시간 초과와 별개로 틀렸습니다!가 나오는 코드입니다.

// i = 행, j = 열

// 방문 했다는 표시
visited[i][j] = true
    
// 방문 안한 경우 if문 실행
if !visited[i][j] {
    ...
}

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

문제

문제

출처

ICPC

2468 swift 시간초과 이유가 궁금합니다.

glorylk 2년 전 0

wapas 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말