백준 7569번 토마토 - 스위프트(Swift) 풀이 + 그림 설명

1. 토마토를 그래프의 정점으로 생각한다.
2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다.
3. 마지막에 안 익은 토마토가 있는지 확인한다.

---

1. 토마토를 그래프의 정점으로 생각한다.

 들어있지 않은 칸은 무시하고, 토마토들을 그래프의 정점으로 생각한다. 전체 상자를 그래프로 바꾸어줄 것이다.

 

2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다.

 빨간색은 익은 토마토이고, 초록색은 안 익은 토마토를 나타내었다. 빨간색 정점에 적힌 숫자는 첫 날로부터 며칠 후에 익었는지를 기록한 것이다.

 처음부터 3개의 토마토가 익어있는 아래와 같은 상황이라고 하자.

 

 

 하루가 지나 1일 째가 되면, 바로 옆에 붙어있는 초록색 토마토 3개가 추가로 아래와 같이 익게 된다.

 

 

 하루가 더 지나 이틀 째가 되면, 남아있는 토마토가 모두 익게 된다.

 

 

 결국 토마토가 익는 과정이 너비 우선 탐색(BFS) 과정과 같음을 알 수 있다!

 따라서 처음부터 익어있는 토마토들을 큐에 다 넣어주고, 큐가 빌 때까지 큐에서 토마토를 뽑아 그 토마토와 인접한 토마토들을 익혀주자.

 큐에 토마토를 넣을 때, 그 토마토가 며칠 째에 익었는지를 같이 담아주면, 그 토마토의 인접한 토마토가 며칠째에 익는지를 쉽게 알 수 있다.

 

3. 마지막에 안 익은 토마토가 있는지 확인한다.

 모든 토마토가 익을 수 없는 경우도 있다. 아래와 같이 고립되어있으면, 끝까지 못 익은 상태로 끝난다.

 이것을 체크해주기 위해 마지막에 0인 토마토가 있는지 확인하는 것에 유의하면 된다.

 

---

import Foundation

var M = 0, N = 0, H = 0
var box = Array(repeating: Array(repeating: Array(repeating: -1, count: 102), count: 102), count: 102)

typealias Tomato = (x: Int, y: Int, z: Int, day: Int)   // day = 익은 날짜
typealias Adjacent = (dx: Int, dy: Int, dz: Int)

struct Queue {
    var queue = [Tomato]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func insert(_ tomato: Tomato) {
        queue.append(tomato)
    }
    
    mutating func popFront() -> Tomato {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func BFS() -> Int {
    var queue = Queue()
    var maxDay = 0
    
    for i in 1...H {
        for j in 1...N {
            for k in 1...M {
                if box[i][j][k] == 1 {      // 처음부터 익어있던 토마토
                    queue.insert((i, j, k, 0))
                }
            }
        }
    }
    
    while !queue.isEmpty {
        let current = queue.popFront()
        
        let adjacents: [Adjacent] = [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]
        for adj in adjacents {
            let adjX = current.x + adj.dx
            let adjY = current.y + adj.dy
            let adjZ = current.z + adj.dz
            let adjDay = current.day + 1
            
            if box[adjX][adjY][adjZ] == 0 {     // 인접한 칸에 안익은 토마토가 있는 경우
                box[adjX][adjY][adjZ] = 1       // 영향을 받아 익음
                maxDay = max(maxDay, adjDay)
                queue.insert((adjX, adjY, adjZ, adjDay))
            }
        }
    }
    
    for i in 1...H {
        for j in 1...N {
            for k in 1...M {
                if box[i][j][k] == 0 {          // 익지 못한 토마토가 있는 경우
                    maxDay = -1
                    break
                }
            }
        }
    }
    
    return maxDay
}

func solution() {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    M = input[0]
    N = input[1]
    H = input[2]
    
    for i in 1...H {
        for j in 1...N {
            input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            input.enumerated().forEach{ box[i][j][$0+1] = $1 }
        }
    }
    
    print(BFS())
}

solution()