문제 링크 (opens new window)

문제 설명

1. 가로 M칸, 세로 N칸 2차원 배열에 토마토 삽입
2. -1은 빈칸, 0은 익지 않은 토마토, 1은 익은 토마토
3. 익은 토마토는 상하좌우 인접한 익지 않은 토마토를 익힌다.
4. 모든 토마토가 익을 때 까지 소요된 시간

접근 방식

1. 초기 입력 시 익은 토마토 좌표를 배열에 저장한다.
2. 익은 토마토들을 시작으로 BFS
3. 플러드필 알고리즘을 적용하여 매 try에 저장된 큐 사이즈 만큼만 BFS를 돌린다.
4. 각 BFS try가 끝나면 하루가 소요된 것
5. BFS 종료 후 전체 토마토 상태 확인, 안 익은게 여전히 존재하면 완전히 분리된 토마토로 간주하여 -1 출력
6. 모두 익어있으면 소요된 시간 출력

풀이

1. BFS풀이
2. 플러드필 알고리즘 적용

import Foundation

let MN = readLine()!.split(separator: " ").map { Int($0)! }; let M = MN[1]; let N = MN[0]
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: 1005), count: 1005)
var adj: [[Int]] = .init(repeating: .init(repeating: -1, count: N+5), count: M+5)
var pos: [(Int, Int)] = []
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var ret = 0

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 array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

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

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

func bfs() {
    while !q.isEmpty {
        let qSize = q.count
        ret += 1
        for _ in 0..<qSize {
            guard let here = q.dequeue() else { return }
            for i in 0..<4 {
                let ny = dy[i] + here.0
                let nx = dx[i] + here.1

                if ny >= M || nx >= N || ny < 0 || nx < 0 || visited[ny][nx] || adj[ny][nx] == -1 || adj[ny][nx] == 1 {
                    continue
                }

                q.enqueue((ny, nx))
                adj[ny][nx] = 1
                visited[ny][nx] = true
            }
        }
    }
}

func check() -> Bool {
    for row in 0..<M {
        for col in 0..<N {
            if adj[row][col] == 0  {
                return false
            }
        }
    }

    return true
}

for row in 0..<M {
    adj[row] = readLine()!.split(separator: " ").enumerated().map { (col, value) in
        let tomato = Int(value)!
        if tomato == 1 {
            q.enqueue((row, col))
        }
        return tomato
    }
}

bfs()
print(check() ? ret - 1 : -1)