99클럽 코테 스터디 4기 12일차 TIL - 백준: 토마토(7569) Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	7569	토마토	BFS	골드5	Swift

🚀 나의 접근 방법

이 문제는 토마토(7576) 문제와 거의 비슷하다. 2차원 배열을 3차원 배열로, 탐색 이동을 상하좌우가 아닌 위, 아래, 왼쪽, 오른쪽, 앞, 뒤로 해주면 된다.

익은 토마토와 인접한 토마토들이 순차적으로 익어 간다는 것에서 BFS를 사용해야 된다는 것을 알아차릴 수 있다.

토마토 상자가 한 판만 있는게 아니라 여러 판이 쌓여있는 구조이므로 3차원 배열로 상자 그래프를 정의해줘야 한다.

그리고 BFS를 진행하기 전에 먼저 처음 상태(처음 입력된 토마토의 상타)에서 익은 토마토들의 위치를 BFS 큐에 넣어 줘야 한다. 왜냐하면 BFS를 하려면 탐색의 시작점이 필요하고, 탐색의 시작점은 익어있는 토마토여야 한다.

3차원에서의 이동방향은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤로 아래와 같이 정의 가능하다.

let dx = [0,  0, -1, 1,  0, 0]
let dy = [0,  0,  0, 0, -1, 1]
let dz = [1, -1,  0, 0,  0, 0]

상자와 똑같은 크기의 visitedDate 배열을 만들어 각 토마토가 익는데 며칠이 걸렸는지 기록했다. 그리고 기록을 할 때마다 마지막으로 익은 토마토의 인덱스를 lastIdx에 저장하여 마지막으로 익은 토마토의 visitedDate에 접근하도록 했다.

✍️ 나의 코드

Swift

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (M, N, H) = (input[0], input[1], input[2])

var graph: [[[Int]]] = []

for _ in 0..<H {
    var g: [[Int]] = []
    for _ in 0..<N {
        g.append(readLine()!.split(separator: " ").map{ Int($0)! })
    }
    graph.append(g)
}

var queue: [(Int, Int, Int)] = []

for h in 0..<H {
    for n in 0..<N {
        for m in 0..<M {
            if graph[h][n][m] == 1 {
                queue.append((h, n, m))
            }
        }
    }
}

let dx = [0,  0, -1, 1,  0, 0]
let dy = [0,  0,  0, 0, -1, 1]
let dz = [1, -1,  0, 0,  0, 0]

var visitedDate: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: 0, count: M), count: N), count: H)
var lastIdx = (0, 0, 0)

func bfs() {
    var idx = 0
    
    while queue.count > idx {
        let n = queue[idx]
        let date = visitedDate[n.0][n.1][n.2]
        
        for i in 0..<6 {
            let nx = n.2 + dx[i]
            let ny = n.1 + dy[i]
            let nz = n.0 + dz[i]
            
            if nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1 || nz < 0 || nz > H - 1 {
                continue
            }
            
            if graph[nz][ny][nx] == -1 || graph[nz][ny][nx] == 1{
                continue
            }
            
            graph[nz][ny][nx] = 1
            queue.append((nz, ny, nx))
            visitedDate[nz][ny][nx] = date + 1
            lastIdx = (nz, ny, nx)
        }
        idx += 1
    }
}

bfs()

var isOk = true

if graph.contains(where: {$0.contains(where: {$0.contains(0)})}) {
    isOk = false
}

if isOk {
    print(visitedDate[lastIdx.0][lastIdx.1][lastIdx.2])
} else {
    print(-1)
}

🤔