[Algorithm] 백준 - 7576번 토마토 (Swift)

문제 소개

https://www.acmicpc.net/problem/7576

토마토가 다 익는 시간을 구하는 문제이다. 익은 토마토부터 번져나가는(?) 시간을 구하는 것이다.
 

문제 풀이

bfs를 활용하여 풀었다. 문제는 queue를 활용하긴 했지만 removeFirst의 시간복잡도가 O(n)이였기 때문에 시간초과 문제가 났다. 그래서 removeFirst와 똑같은 효과가 나게 하여 index를 활용하여 문제를 풀었다.

import Foundation

let mn = readLine()!.split(separator: " ").map { Int($0)! }
let (m, n) = (mn[0], mn[1])

var box = [[Int]]()
var queue = [(Int, Int)]()

for i in 0..<n {
    let tomato = readLine()!.split(separator: " ").map { Int($0)! }
    box.append(tomato)
    
    for j in 0..<m {
        if tomato[j] == 1 {
            queue.append((i, j))
        }
    }
}

var idx = 0

while queue.count >= idx + 1 {
    let poped = queue[idx]
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for direction in directions {
        let i = poped.0 + direction.0
        let j = poped.1 + direction.1
        
        if i >= 0 && i < n && j >= 0 && j < m && box[i][j] == 0 {
            box[i][j] = box[poped.0][poped.1] + 1
            queue.append((i, j))
        }
    }
    
    idx += 1
}

var answer = 0

loop: for i in 0..<n {
    for j in 0..<m {
        if box[i][j] == 0 {
            answer = -1
            break loop
        } else {
            answer = max(answer, box[i][j]-1)
        }
    }
}

print(answer)