99클럽 코테 스터디 12일차 TIL: 3차원 그래프

문제

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

풀이

토마토 문제와 비슷한 문제이다.
조금 다른점이 하나 있는데 높이가 추가되었다는 점이다.

기존에 상하좌우로 퍼졌던 토마토가, 상하좌우 위아래(?) 두 방향이 추가되었다.

나는 이런 문제를 풀 때, 기존에 방향을 설정해줄 변수로 dy, dx을 다음과 같이 정의하였다.

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

북동남서 방향으로 시계방향으로 정의하였었는데, 이제 추가로 z축도 필요하다고 생각했다.
그래서 방향을 다음과 같이 정의했다.

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

여기까지 이해했다면 반은 풀었다고 볼 수 있다.

익숙하지 않게 3차원 배열을 선언하고 입력으로 받은 배열값을 넣어줬다.

var graph = [[[Int]]](repeating: [], count: h)
for i in 0..<h {
    for _ in 0..<m {
        graph[i].append(readLine()!.split { $0 == " " }.map { Int($0)! })
    }
}

진짜 다풀었다.
토마토가 모두 익는 최소 일수를 구해야하므로 BFS 알고리즘으로 풀어야겠다고 생각했다.

queue 자료구조를 사용할 것이고, 1의 위치를 queue에 넣어주자.

for z in 0..<h {
    for y in 0..<m {
        for x in 0..<n {
            if graph[z][y][x] == 1 {
                queue.append((z, y, x))
            }
        }
    }
}

또한 상하좌우위아래로 이동하면서 graph의 범위를 벗어나는지 확인하기 위한 메서드를 하나 정의해줬다.

func isValidCoord(z: Int, y: Int, x: Int) -> Bool {
    return 0..<h ~= z && 0..<m ~= y && 0..<n ~= x
}

이제 1의 위치들에서 부터 BFS를 수행하자.
범위를 벗어나지 않고, 다음 토마토가 0이라면 이동이 가능하다.
여기선 visited 배열을 선언하지 않았고, 1부터 시작해서 이동이 가능한 좌표라면 나의 현재좌표 + 1을 넣어주려고 한다.

for i in 0..<6 {
    let nz = z + dz[i]
    let ny = y + dy[i]
    let nx = x + dx[i]

    if isValidCoord(z: nz, y: ny, x: nx) && graph[nz][ny][nx] == 0 {
        graph[nz][ny][nx] = graph[z][y][x] + 1
        queue.append((nz, ny, nx))
    }

}

마지막으로 이 3차원 배열에 0이 존재하는지 확인을 해주어야 한다.
존재한다면 -1을 출력하고, 존재하지 않는다면 가장 큰 값에서 -1을 해줘야 일수가 나온다.

전체 코드는 다음과 같다.

소스코드

후기

살짝 머리아픈 문제 그래도 재밌는 문제였다.