1. 문제 설명

토마토

2. 문제 분석

탐색 알고리즘으로 행렬 그래프를 탐색하면서 마킹하면서 최대 비용을 기록한다. 탐색을 마친 뒤 행렬 그래프 중 0이 남아 있다면 탐색 불가능한 지역이 남아 있다는 뜻이다.

• 스위프트는 큐가 없기 때문에 BFS를 사용할 때 구현해주어야 한다. 팝 구현을 배열의 removeAtFirst로 사용하면 시간 복잡도가 O(N)이 나오기 때문에 시간 초과가 나온다... 사실 BFS보다 큐 구현에 필요한 배열 두 개 사용 방법이 더 까다롭다.

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
}