문제 링크 (opens new window)

문제설명

1. Z축 상하, XY축 상하좌우 기준으로 총 6방향으로 토마토가 익어간다.
2. 처음부터 모든 토마토가 익어있으면 0을 출력한다.
3. 벽에 막혀서 절대 익히지 못하는 토마토가 있으면 -1을 출력한다.
4. 전체 토마토가 익을때까지 소요되는 시간을 출력한다.

접근 방식

1. 방향 설정을 잘못했다. Z축 대각선 방향을 고려하여 {-1, 0, 1}과 for문 3중 중첩을 활용했었다.
2. 그럴 필요 없이 정확한 특정 한 방향에 따른 XYZ 변화량만 계산하면 된다.
3. 플러드필 알고리즘을 써서 토마토가 익기까지의 소요 시간을 체크한다.

풀이

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let MNH = readLine()!.split(separator: " ").map { Int($0)! }; let M = MNH[0]; let N = MNH[1]; let H = MNH[2]

var adj: [[[Int]]] = .init(repeating: .init(repeating: .init(repeating: -1, count: M), count: N), count: H)
var visited: [[[Bool]]] = .init(repeating: .init(repeating: .init(repeating: false, count: M), count: N), count: H)
var tomato: [(Int, Int ,Int)] = []
let dz = [-1, 1, 0, 0, 0, 0]; let dy = [0, 0, -1, 0, 1, 0]; let dx = [0, 0, 0, 1, 0, -1]
var ret = 0
var riped = true

for height in 0..<H {
    for row in 0..<N {
        adj[height][row] = readLine()!.split(separator: " ").enumerated().map { (col, value) in
            let value = Int(value)!
            if value == 1 { tomato.append((height, row, col)) }
            if value == 0 { riped = false }
            return value
        }
    }
}

var q = Queue<(Int, Int, Int)>()

for t in tomato {
    q.enqueue(t)
    visited[t.0][t.1][t.2] = true
}

while !q.isEmpty {

    let size = q.count

    for _ in 0..<size {
        guard let there = q.dequeue() else { break }

        for i in 0..<6 {
            let nz = dz[i] + there.0
            let ny = dy[i] + there.1
            let nx = dx[i] + there.2

            if nz < 0 || ny < 0 || nx < 0 || nz >= H || ny >= N || nx >= M || visited[nz][ny][nx] || adj[nz][ny][nx] == -1 {
                continue
            }
            adj[nz][ny][nx] = 1
            visited[nz][ny][nx] = true
            q.enqueue((nz, ny, nx))
        }
    }

    ret += 1
}

func check() -> Bool {
    if riped {
        ret = 0
        return true
    }

    for i in 0..<H {
        for j in 0..<N {
            for k in 0..<M {
                if adj[i][j][k] == 0 {
                    return false
                }
            }
        }
    }
    return true
}

check() ? print(ret > 0 ? ret - 1 : ret) : print(-1)