글 읽기 - 속도 차이가 왜 심한가요?

iyeaaa 1년 전 0

밑에 코드가 제가 작성한건데, 코드가 별로 다를게 없어보이는데도, 속도가 700ms는 차이나네요;;

// realkyuman26 님 코드
let data = readLine()!.split(separator: " ").map { Int(String($0))! }
let rowSize = data[0], columnSize = data[1]
var map = [[Character]]()
let directionMove = [(0, 1), (0, -1), (1, 0), (-1, 0)] // 東西南北

//mapのデータを格納する
for _ in 0..<rowSize {
    map += [Array(readLine()!)]
}

print(settingStartPoint())

//全ての陸地(L)からstartする経路を探索し、bfs_TreasureIslance関数を呼び出して最長距離を探す
func settingStartPoint() -> Int {
    var result = 0
    for i in 0..<rowSize {
        for j in 0..<columnSize {
            // Lがあるところを完全探索する
            if map[i][j] == "L" {
                result = max(result, bfs_TreasureIsland(i, j))
            }
        }
    }
    
    return result
}

//BFSアルゴリズムを用いた最長距離探し
func bfs_TreasureIsland(_ rowStart: Int, _ columnStart: Int) -> Int {
    var neededVisitQueue = [(rowStart, columnStart)]
    var distance = Array(repeating: Array(repeating: -1, count: columnSize), count: rowSize) // それぞれの場所に着く時間を-1として初期化 , また、-1であることはまだ、訪問したことない場所であることを示す
    var index = 0
    var tempDistance = 0 //start地点に指定した場所から距離を測る
    distance[rowStart][columnStart] = 0
    
    while index < neededVisitQueue.count {
        let (currentRow, currentColumn) = neededVisitQueue[index]
        
        for i in 0..<4 {
            let (nextRow, nextColumn) = (currentRow + directionMove[i].0, currentColumn + directionMove[i].1)
            
            if nextRow < 0 || nextRow >= rowSize || nextColumn < 0 || nextColumn >= columnSize {
                continue
            }
            if distance[nextRow][nextColumn] != -1 || map[nextRow][nextColumn] == "W" {
                continue
            }
            neededVisitQueue.append((nextRow, nextColumn))
            distance[nextRow][nextColumn] = distance[currentRow][currentColumn] + 1
            tempDistance = max(tempDistance, distance[nextRow][nextColumn]) //距離が最大となるように更新
        }
        index += 1
    }
    
    return tempDistance
}

-----------------------------------------------------------------------------------


let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var graph = [[Character]]()

solveProblem()

func solveProblem() {
    inputGraph()
    findMaxDist()
}

func findMaxDist() {
    var answer = 0
    for i in 0..<n {
        for j in 0..<m {
            if graph[i][j] == "L" {
                answer = max(answer, bfs(i, j))
            }
        }
    }
    print(answer)
}

func inputGraph() {
    for _ in 0..<n {
        graph += [Array(readLine()!)]
    }
}

func bfs(_ i: Int, _ j: Int) -> Int {
    var visit = [[Int]](repeating: [Int](repeating: -1, count: m), count: n)
    visit[i][j] = 0
    var max = 0
    var index = 0
    var queue = [[i, j]]
    while index < queue.count {
        let (x, y) = (queue[index][0], queue[index][1])
        for i in [[-1, 0], [0, -1], [1, 0], [0, 1]] {
            let (nx, ny) = (x+i[0], y+i[1])
            if (0..<n).contains(nx) && (0..<m).contains(ny) {
                if graph[nx][ny] == "L" && visit[nx][ny] == -1 {
                    queue.append([nx, ny])
                    visit[nx][ny] = visit[x][y] + 1
                    if max < visit[nx][ny] {
                        max = visit[nx][ny]
                    }
                }
            }
        }
        index += 1
    }
    return max
}

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

문제

문제

출처

ICPC

속도 차이가 왜 심한가요?

iyeaaa 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말