[Swift 백준] 7569 토마토

 

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

 

풀이 아이디어

그래프 탐색 문제입니다.

Y축까지 있으므로 3차원 배열을 사용합니다.

이동 방향은 기본적인 상하좌우에서 위 아래가 추가된 6개로 이동합니다.

 

자세한 풀이는 아래와 같습니다.

 

풀이

import Foundation

// 가로(m), 세로(n), 높이(h)
let input = readLine()!.split(separator: " ").map { Int($0)! }
let m = input[0], n = input[1], h = input[2]

// 3차원 배열 graph[h][n][m] 초기화
var graph = [[[Int]]]()
for _ in 0..<h {
    var level = [[Int]]()
    for _ in 0..<n {
        let row = readLine()!.split(separator: " ").map { Int($0)! }
        level.append(row)
    }
    graph.append(level)
}

// 햇갈려서 바꿧습니다
// BFS를 위한 큐 (z: 높이, y: 행, x: 열)
var queue = [(z: Int, y: Int, x: Int)]()

// 처음부터 익은 토마토 (값이 1인 곳)를 큐에 추가
for z in 0..<h {
    for y in 0..<n {
        for x in 0..<m {
            if graph[z][y][x] == 1 {
                queue.append((z, y, x))
            }
        }
    }
}

// 6방향: 상하, 좌우, 위아래 (z축)
let dz = [0, 0, 0, 0, 1, -1]
let dy = [1, -1, 0, 0, 0, 0]
let dx = [0, 0, 1, -1, 0, 0]


var index = 0
while index < queue.count {
    let current = queue[index]
    index += 1
    
    for i in 0..<6 {
        let nz = current.z + dz[i]
        let ny = current.y + dy[i]
        let nx = current.x + dx[i]
        
        // 범위 체크
        if nz < 0 || nz >= h || ny < 0 || ny >= n || nx < 0 || nx >= m {
            continue
        }
        
        // 익지 않은 토마토(0)를 만난 경우, 날짜를 갱신 후 큐에 추가
        if graph[nz][ny][nx] == 0 {
            graph[nz][ny][nx] = graph[current.z][current.y][current.x] + 1
            queue.append((nz, ny, nx))
        }
    }
}

// 아직 0인 토마토가 있으면 -1 출력, 아니면 최대 날짜-1 출력
var answer = 0
for level in graph {
    for row in level {
        for tomato in row {
            if tomato == 0 {
                print(-1)
                exit(0)
            }
            answer = max(answer, tomato)
        }
    }
}
print(answer - 1)