[Swift] 백준_토마토(7569)

문제

 

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

7569번: 토마토

 

 

풀이

 

이전의 토마토문제와 유사한 문제이며 dz만 생각해주면 쉽게 풀 수 있다.

 

마찬가지로 BFS를 돌리기전에 미리 큐에 모든 1짜리 토마토를 넣어준다.

다음으로 큐에서 하나씩 확인하며 dx, dy, dz를 1씩 더한 것 중 조건을 만족하며 tomato[newZ][newX][newY]가 0인 것들에 대해서만 기존의 값에서 1을 추가한 뒤 큐에 [newZ,newX,newY]를 넣어주었다.

 

이때 newZ, newX, newY 순서로 넣은 이유는 단순히 코드를 그렇게 짰기 때문이다.

 

이 문제에서도 배열 두 개를 이용한 큐 대신 배열하나와 인덱스를 이용하여 큐를 이용하였다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var queue: [[Int]] = []
let dx = [1,0,-1,0,0,0]
let dy = [0,1,0,-1,0,0]
let dz = [0,0,0,0,1,-1]
var tomato: [[[Int]]] = []
var minDay = 1
for _ in 0..<input[2] {
    var temp: [[Int]] = []
    for _ in 0..<input[1] {
        temp.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }
    tomato.append(temp)
}

//1인 토마토 큐에 넣기
for i in 0..<input[2] {
    for j in 0..<input[1] {
        for k in 0..<input[0] {
            if tomato[i][j][k] == 1 {
                queue.append([i,j,k]) //i가 높이, j가 행, k가 열
            }
        }
    }
}
//BFS
var idx = 0
while idx < queue.count {
    let current = queue[idx]
    idx += 1
    for i in 0..<dx.count {
        let newX = current[1] + dx[i] //행
        let newY = current[2] + dy[i] //열
        let newZ = current[0] + dz[i] //높이
        if newX < 0 || newY < 0 || newZ < 0 || newX >= input[1] || newY >= input[0] || newZ >= input[2] {
            continue
        }
        if tomato[newZ][newX][newY] == 0 {
            tomato[newZ][newX][newY] = tomato[current[0]][current[1]][current[2]] + 1
            minDay = max(minDay, tomato[newZ][newX][newY])
            queue.append([newZ,newX,newY])
        }
    }
}
minDay -= 1
for i in 0..<input[2] {
    for j in 0..<input[1] {
        for k in 0..<input[0] {
            if tomato[i][j][k] == 0 {
                minDay = -1
                break
            }
        }
    }
}
print(minDay)

 

_____________________________________________________________________________________________________

 

BFS 문제들을 풀다보니 위처럼 dx, dy를 이용해 주변을 확인하는 방법을 자주 쓰는데, 이때 행이랑 열중 어떤 것을 x로 둘지 확실하게 정해서 익숙해져야 할 것 같다.

이차원에서는 괜찮았는데 3차원이되니 좀 많이 헷갈렸다.