[Algorithm] 토마토

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/7576

💬 Idea

토마토가 모두 익을 때까지의 최소 날짜를 구하기 위해서 BFS를 수행하자.

1. N X M 크기의 tomatos 2차원 배열을 만든다.
2. 저장될 때부터 익혀진 토마토(1)의 좌표를 찾아 ripeTomatos 배열에 저장해준다.
3. 만약 저장될 때부터 모든 토마토가 익어있는 상태라면 0을 출력하고, 그렇지 않으면 bfs를 수행한다.
4. bfs를 수행하기에 앞서 queue에 시작 좌표인 ripeTomatos들을 저장해준다.
   1. 1이 여러 개인 경우 여러 지점에서 출발해 토마토를 익혀야함.
5. 이후 queue의 원소를 꺼내면서 상 하 좌 우 좌표에 위치한 토마토들을 익힌다.
6. bfs가 수행된 이후 모든 토마토가 익었다면 토마토가 모두 익기까지의 최소 날짜를 출력하고, 그렇지 않다면 -1을 출력한다.

💬 풀이

import Foundation

func solution7576() {
    let box = readLine()!.split(separator: " ").map({ Int(String($0))! })
    var tomatos: [[Int]] = []
    var ripeTomatos: [[Int]] = []
    var lastDay = 0
    var isFirstAllRipe = true
    
    for n in 0..<box[1] {
        let tomato = readLine()!.split(separator: " ").map({ Int(String($0))! })
        tomatos.append(tomato)
        
        // 좌표 1 찾기
        for (mdx, m) in tomato.enumerated() {
            if m == 1 {
                ripeTomatos.append([n, mdx])
            } else if m == 0 {
                isFirstAllRipe = false
            }
        }
    }
    
    func bfs() {
        var queue: [[Int]?] = ripeTomatos // queue는 FIFO이므로 이미 익은 좌표들부터 차례로 방문하여 토마토를 익힐 수 있다.
        var pointer = 0
        
        let dx = [-1, 1, 0, 0]
        let dy = [0, 0, -1, 1]
        
        while pointer < queue.count {
            let cx = queue[pointer]![0]
            let cy = queue[pointer]![1]
            queue[pointer] = nil
            pointer += 1
            
            for i in 0...3 {
                let nx = cx + dx[i]
                let ny = cy + dy[i]
                
                if nx < 0 || ny < 0 || nx > tomatos.count - 1 || ny > tomatos[0].count - 1 {
                    continue
                }
                
                if tomatos[nx][ny] == -1 {
                    continue
                }
                
                if tomatos[nx][ny] == 0 {
                    tomatos[nx][ny] = tomatos[cx][cy] + 1
                    queue.append([nx, ny])
                    lastDay = tomatos[nx][ny] - 1
                }
            }
        }
    }
    
    var isAllRipe = true
    
    // 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0 출력
    if isFirstAllRipe {
        print(0)
    } else {
        bfs()
        
        for i in tomatos {
            if i.contains(0) {
                isAllRipe = false
            }
        }
        
        if isAllRipe {
            print(lastDay)
        } else {
            // 토마토가 모두 익지는 못하는 상황이면 -1을 출력
            print(-1)
        }
    }
}

bfs를 수행할 때 queue의 첫번째 원소를 꺼내기 위해 removeFirst()를 사용한다면 시간초과가 발생할 수 있어 포인터의 원리를 이용하여 풀이해주었다.