[백준] BFS - 7576번 토마토

7576번: 토마토

 

입력 & 출력

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.
보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

 

풀이

BFS 문제로, 익지 않은 토마토(0)을 탐색하며 각 칸에 도착하기 위한 최소 거리를 구한다. 
모든 칸을 돌았으나 익지 않은 토마토가 있을 경우, -1을 출력한다.

이 여부는 전체 개수를 구한 후 토마토가 없는 경우와 익은 토마토의 개수를 빼어 Total 로 선언한다.
Queue에 담긴 토마토를 뺄 때마다 Total 값을 1씩 빼어 모든 칸을 돌고 난 후 Total 이 0이면 모든 토마토가 익었다는 것으로 간주한다.

Swift 전체 코드

    let num = readLine()!
    let width = Int("\(num.first!)")!
    let height = Int("\(num.last!)")!
    
    var box : [[Int]] = .init(repeating: [], count: height)
    var queue : [(h: Int, w: Int, days: Int)] = []
    
    var total = width * height
    var days = 0
    
    let dx = [-1, 0, 1, 0]
    let dy = [0, -1, 0, 1]
    
    for i in 0..<height {
        let line = readLine()!.split(separator: " ")
        
        for j in 0..<line.count {
            if Int(line[j])! == -1 {
                total -= 1
            } else if Int(line[j])! == 1 {
                queue.append((i,j,days))
            }
            box[i].append(Int(line[j])!)
        }
    }
    
    while !queue.isEmpty {
        let pop = queue.remove(at: 0)
        total -= 1
        
        if pop.days > days {
            days = pop.days
        }
        
        for j in 0...3 {
            let y = pop.w + dx[j]
            let x = pop.h + dy[j]
            
            if x < 0 || x >= height || y < 0 || y >= width {
                continue
            }
            
            if box[x][y] == -1 || box[x][y] == 1  {
                continue
            }
            
            box[x][y] = 1
            queue.append((x,y,days + 1))
        }
    }
    
    print(total != 0 ? -1 : days)

 

 

+ 채점결과 2%의 경우는 시간 초과로 removeFirst() 대신 Queue를 구현해서 사용해야한다. (추후 업데이트)