7576 토마토

Today 8/16

BFS

queue를 사용하는 FIFO형식의 탐색방법이다.

토마토 (My Code)

//7576 토마토
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])

var box = [[Int]]()
var queue = [(Int, Int)]()
var index = 0
var output = 0

for row in 0..<N {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    for (i, col) in line.enumerated() {
        if col == 1 {
            queue.append((row, i))
        }
    }
    box.append(line)
}

while index < queue.count {
    let node = queue[index]
    for i in [(-1, 0),(1, 0),(0, -1),(0, 1)] {
        let (m, n) = (node.0+i.0, node.1+i.1)
        if (0..<N).contains(m) && (0..<M).contains(n) && box[m][n] == 0 {
            queue.append((m, n))
            box[m][n] = box[node.0][node.1]+1
        }
    }
    index += 1
}

for row in 0..<N {
    if box[row].contains(0) {
        output = -1
        break
    } else if let max = box[row].max(), output < max {
        output = max-1
    }
}
print(output)

removeFirst()하면 시간초과가 나서 index를 사용해야했다.

enumerated()를 통해 box배열을 만들면서 같이 queue를 뽑았고, 옵셔널 바인딩을 통해 max값을 찾아냈다. 조건도 함께 걸어주려면 &&가 아닌 콤마를 통해 병기한다는 것을 배웠다.

원래는 3개의 인자를 가진 tuple을 이용하려했는데, 1씩 늘어나니까 그냥 box배열에다가 root값 + 1을 넣어주면 더 간소화된다는 것을 알고 수정했다.