[Swift] 7576번: 토마토 문제 풀이 [BOJ - Gold5]

💬 문제

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

7576번: 토마토

 

---

💬 Idea

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

1. N X M 크기의 tomatos 2차원 배열을 만든다.
2. 저장될 때부터 익혀진 토마토 (=1)의 좌표를 찾아 ripeTomatos 배열에 저장해준다.
3. 만약 저장될 때부터 모든 토마토가 익어있는 상태라면 0을 출력하고, 그렇지 않으면 bfs를 수행한다.
4. bfs를 수행하기에 앞서 queue에 시작 좌표인 ripeTomatos들을 저장해준다.
   • ✅ 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()를 사용한다면 시간초과가 발생할 수 있기 때문에
본 풀이에서는 포인터의 원리를 이용하여 풀이해보았다 😊

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Boj/7576_%ED%86%A0%EB%A7%88%ED%86%A0.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift