1.問題の説明

名トマト

2.問題分析

プローブアルゴリズムを用いてマトリクス図をプローブし,マーキングしながら最大費用を記録した.検索終了後にマトリクスマップに0が残っている場合は、検索できない領域が残っていることを意味します.

swiftにはキューがないので、BFSを使用する場合に実装する必要があります.配列としてpop実装を用いたremoveAtFirstでは,時間的複雑度O(N)が出現し,タイムアウトが発生する.実際,BFSに比べてキューを実現するために必要な2つの配列の使用方法はより困難である.

3.私の回答

import Foundation

struct Queue<T: Equatable> {
    var enqueue: [T] = []
    var dequeue: [T] = []
    
    init() {}
    
    init(_ queue: [T]) {
        enqueue = queue
    }
    
    mutating func push(_ element: T) {
        enqueue.append(element)
    }
    
    mutating func pop() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
    mutating func remove() {
        enqueue.removeAll()
        dequeue.removeAll()
    }
    
    var isEmpty: Bool {
        return enqueue.isEmpty && dequeue.isEmpty
    }
    
    var firstIndex: T? {
        if dequeue.isEmpty {
            return enqueue.first
        } else {
            return dequeue.last
        }
    }
    
    var lastIndex: T? {
        if enqueue.isEmpty {
            return dequeue.first
        } else {
            return enqueue.last
        }
    }
    
    var count: Int {
        return enqueue.count + dequeue.count
    }
    
    func contains(_ element: T) -> Bool {
        return enqueue.contains(element) || dequeue.contains(element)
    }
}

let input = readLine()!.split(separator:" ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])
let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]
var nodes: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N{
    let line = readLine()!.split(separator:" ").map{Int(String($0))!}
    nodes[i] = line
//  인접 행렬 구현
}

var startNodes:[[Int]] = []
for i in 0..<N{
    for j in 0..<M{
        if nodes[i][j] == 1{
            startNodes.append([i, j, 0])
        }
    }
}

var answer = BFS(startNodes:startNodes)

for i in 0..<N{
    if nodes[i].contains(0){
        answer = -1
        break
    }
}
print(answer)

func BFS(startNodes:[[Int]]) -> Int{
    var queue: Queue = Queue(startNodes)
    var total = 0
    while queue.isEmpty == false{
        let input = queue.pop()!
//      removeAtFirst를 사용하며 시간 초과 -> 배열 두 개를 통한 큐 구현
        let (curRow, curCol, curCnt) = (input[0], input[1], input[2])
        total = max(total, curCnt)
        
        for i in 0..<4{
            let nextRow = curRow + dy[i]
            let nextCol = curCol + dx[i]
            if nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M{
                continue
            }
            
            if nodes[nextRow][nextCol] == 0{
                nodes[nextRow][nextCol] = 1
                queue.push([nextRow, nextCol, curCnt+1])
            }
        }
    }
    return total
}