글 읽기 - [Swift] 7576 토마토 2%에서 시간초과

yabby1997 3년 전 0

매번 C++로 문제를풀다 최근 iOS개발을 도전하면서 Swift로 문제들을 풀어보고있습니다.

BFS를 연습할겸 저번에 C++로 풀었던 7569토마토문제와 비슷한 7576번 토마토문제를 Swift로 풀었는데요

도대체 어디서 시간초과가 발생하는지 모르겠습니다...

입력부분에서 토마토 상자 크기를 지정해주지 않아서 그런것인가 싶어서 그 부분도 바꿔보고,

익지않은 토마토가 있었는지 확인하는 방식에 문제가 있는것인가 싶어 그 부분도 여러번 바꿔보았습니다.

그러나 결과는 계속 2%에서 시간초과네요..

C++로는 이렇게 비상식적(?)으로 시간초과를 많이 당해본적이 없어서..굉장히 당황스럽습니다.

어쩌면 C++의 우수한 성능으로 저의 바보같은 코드가 통과한것이었을지도 모르겠네요 ㅜㅜ

지적해주시면 그 부분 고쳐보고 꼭 제것으로 만들어보겠습니다. 감사합니다.

import Foundation

let rowDirection = [-1, 1, 0, 0]
let colDirection = [0, 0, -1, 1]

let size = readLine()!.split(separator: " ").map({Int(String($0))!})
let row = size[1]
let col = size[0]

var tomatoes = Array(repeating: Array(repeating: 0, count:col), count: row)
var tomatoQueue = [[Int]]()

for i in 0..<row {
    let eachRow = readLine()!.split(separator: " ").map({Int(String($0))!})
    for j in 0..<col {
        if eachRow[j] == 1 {
            tomatoQueue.append([i, j])
        }
        tomatoes[i][j] = eachRow[j]
    }
}

BFS()
printResult()

func printResult() {
    var day = 0
    for i in 0..<row {
        for j in 0..<col {
            if tomatoes[i][j] > day {
                day = tomatoes[i][j]
            } else if tomatoes[i][j] == 0 {
                print(-1)
                return
            }
        }
    }
    print(day - 1)
}

func BFS() {
    while !tomatoQueue.isEmpty {
        let tomato = tomatoQueue.removeFirst()
        let originalRow = tomato[0]
        let originalCol = tomato[1]
        for direction in 0...3 {
            let targetRow = originalRow + rowDirection[direction]
            let targetCol = originalCol + colDirection[direction]
            if targetRow >= 0 && targetRow < row && targetCol >= 0 && targetCol < col && tomatoes[targetRow][targetCol] == 0{
                tomatoes[targetRow][targetCol] = tomatoes[originalRow][originalCol] + 1
                tomatoQueue.append([targetRow, targetCol])
            }
        }
    }
}

yabby1997 3년 전 3

해결했습니다.

queue를 list로 구현하는 분들이 많아 저의경우 위 코드에서 그냥 list를 가져와 removeFirst를 dequeue처럼 사용해줬는데요,

removeFirst는 O(n)의 시간복잡도를 갖는다는것이 문제였습니다.

대신 Queue를 list와 from, to 두개의 index정보(투포인터)를 갖는 구조체로 직접 구현해서 dequeue해주도록 했고, 문제없이 통과할 수 있었습니다.

다른분들은 저같은 실수와 삽질 안하시길 바랍니다!!

bigtoy2645 3년 전 0

덕분에 해결했습니다! 감사합니다 ㅜㅜ

yo7504 2년 전 0

감사합니다..덕분에 해결했습니다 ㅠㅠ

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

문제

문제

출처

ICPC

[Swift] 7576 토마토 2%에서 시간초과

yabby1997 3년 전 0

yabby1997 3년 전 3

bigtoy2645 3년 전 0

yo7504 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말