백준 | 7569 토마토 Swift - 그래프

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

 

대표적인 그래프 탐색 문제!!

마지막 토마토가 익는 날까지 최소 며칠이 걸리는지 풀어보는 문제다.ㅋㅋ

 

큐에 익은 토마토 좌표를 넣고,

그 토마토의 상하, 좌우, 위아래까지 확인한 다음

그 토마토가 익은 날짜에 +1을 해서 저장해준다.

그리고 익은 토마토 큐에 넣어주고 또 반복!

 

let temp = readLine()!.split(separator: " ").map({ Int($0)! })
let m = temp[0]
let n = temp[1]
let h = temp[2]

var tomato: [[[Int]]] = Array(repeating: [], count: h)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: h)
var count = 0
var queue = Queue<[Int]>()
var answer = 0

for i in 0..<h {
    for _ in 0..<n {
        tomato[i].append(readLine()!.split(separator: " ").map({ Int($0)! }))
    }
}

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

func dfs(_ z: Int, _ y: Int, _ x: Int) {
    visited[z][y][x] = true
    
    for i in 0..<6 {
        let tempX = x + dx[i]
        let tempY = y + dy[i]
        let tempZ = z + dz[i]
        
        if tempX >= 0 && tempY >= 0 && tempZ >= 0 && tempX < m && tempY < n && tempZ < h {
            if !visited[tempZ][tempY][tempX] && tomato[tempZ][tempY][tempX] == 0 {
                tomato[tempZ][tempY][tempX] = tomato[z][y][x] + 1
                answer = max(answer, tomato[z][y][x])
                queue.enqueue([tempZ, tempY, tempX])
            }
        }
    }
}

func solution() -> Int {
    if !Array(tomato.joined().joined()).contains(0) {
        return answer
    }

    for i in 0..<h {
        for j in 0..<n {
            for k in 0..<m {
                if tomato[i][j][k] > 0 {
                    queue.enqueue([i, j, k])
                }
            }
        }
    }

    while queue.frontValue != queue.size {
        let current = queue.dequeue()!
        let i = current[0]
        let j = current[1]
        let k = current[2]
        if !visited[i][j][k] && tomato[i][j][k] > 0 {
            dfs(i, j, k)
        }
    }

    if Array(tomato.joined().joined()).contains(0) {
        answer = -1
    }

    return answer
}

print(solution())

 

 

다른 그래프 탐색 문제들은 2차원 배열을 사용했다면,

여기서는 3차원 배열을 사용하기 때문에 약간 헷갈리는 부분들이 있었다.

범위 설정!!! 꼭 확인해야 함!!

 

문제를 잘 풀었는데도 시간 초과가 나서 확인해보았는데

Swift Array에서 removeFirst()는 O(n)임을 발견ㅠㅠ

 

https://jeong9216.tistory.com/350#swift%EB%A1%9C-queue-%EA%B5%AC%ED%98%84

[자료구조] Queue(큐) with Swift

이 블로그에서 Swift로 구현한 Queue를 활용해서 풀 수 있었다!! (감사합니다!)