[Algorithm/BOJ] 7569 - 토마토 (BFS) Swift

문제풀이:

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.

-> 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 6가지 방향으로 탐색하여 토마토를 익힌다.

 

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

-> 아래의 그림과 같이 상자에는 익지 않은 토마토, 익은 토마토, 빈 칸이 존재하고 3차원 배열을 이용한다. 

정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

-> 초기 상태에 0인 값이 없다면 0을 반환해주고 탐색이 끝난 후 0이 존재한다면 -1을 반환해준다.

 

위, 아래, 왼쪽, 오른쪽, 앞, 뒤 6가지 방향으로 탐색하면서 처음 상태의 3차원 배열에서 BFS를 이용하여 0인 값(익지 않은 토마토)을 n(영향을 준 토마토)에 1을 더해서 갱신해주면 된다. 

탐색이 끝나고 배열에서 제일 큰 값이 최소 일 수가 되지만 처음 시작할 때 1로 시작하기 때문에 -1을 한 값이 답이 된다.

 

코드:

import Foundation

typealias Tomato = (z: Int, x: Int, y: Int)

func solution() -> Int {
	// 6가지의 방향
    let d = [(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)]
    
    let mnh = readLine()!.split(separator: " ").map { Int(String($0))! }
    let m = mnh[0]
    let n = mnh[1]
    let h = mnh[2]
    var boxes = [[[Int]]](repeating: [[Int]](repeating: [Int](), count: n), count: h)
    var result = 0
    // 토마토 입력 받기
    for z in 0..<h {
        for x in 0..<n {
            let rows = readLine()!.split(separator: " ").map { Int(String($0))! }
            boxes[z][x].append(contentsOf: rows)
        }
    }
    
    var q = [Tomato]()
    
    func bfs() {
        var index = 0

        while index < q.count {
            let now = q[index]
            index += 1
            // 6가지의 방향으로 탐색하기 위해서 6번의 반복문을 돌린다. 
            for i in 0..<6 {
                let nx = now.x+d[i].0
                let ny = now.y+d[i].1
                let nz = now.z+d[i].2
                // 박스 내에서 
                if 0<=nx, nx<n, 0<=ny, ny<m, 0<=nz, nz<h {
                	// 탐색했을 때 0이라면
                    if boxes[nz][nx][ny] == 0 {
                        q.append((nz,nx,ny))
                        // 토마토가 익는 일 수를 갱신해준다. 
                        boxes[nz][nx][ny] = boxes[now.z][now.x][now.y] + 1
                    }
                }
            }
        }
    }
    
    // 탐색 전 익은 토마토의 경우 큐에 넣어준다. 
    for z in 0..<h {
        for x in 0..<n {
            for y in 0..<m {
                if boxes[z][x][y] == 1 {
                    q.append((z,x,y))
                }
            }
        }
    }
    
    bfs()
    
    // 탐색이 끝난 후
    for z in 0..<h {
        for x in 0..<n {
            for y in 0..<m {
            	// 0이 존재한다면 -1 리턴
                if boxes[z][x][y] == 0 {
                    return -1
                }
                // 제일 큰 값이 최소 일수가 된다.
                result = max(result, boxes[z][x][y])
            }
        }
    }
    // 시작했을 때 1을 빼준다. 
    return result == 1 ? 0 : result-1
}

print(solution())

 

문제:

7569번: 토마토