[BOJ] 7579 : 토마토 (3차원 BFS)

백준에 똑같은 명의 7576번 문제 (토마토) 가 있는데 이 문제는 7576번의 3차원 버전의 문제다. 즉 7576번에선 이동하는 좌표를 2개로 놓고 풀수 있지만, 이 문제에선 3차원으로 접근 해야하기 때문에 상, 하, 좌, 우, 위, 아래를 모두 따져야한다. 해당 좌표를 잘 잡을 수 있으면 문제는 2차원 버전과 크게 다르지 않다.

const int dy[] = {0, 0, -1, 1, 0, 0};
const int dx[] = {-1, 1, 0, 0, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};

본인의 경우는 이런식으로 잡았고, 접근할 때 A[nx][ny][nz] 형태로 접근하게 된다. 이 문제를 풀 때 주의할 점은, 2667번

2667번: 단지번호붙이기

문제와 같이 모든 좌표를 돌면서 그 때 그 때 큐에 넣어주면 최단시간을 보장할 수 없다. 왜냐하면 저 문제는 단순히 BFS로 탐색한 영역의 수를 구하는거지만 이 문제는 배열 내에서 숫자가 퍼지는 시간을 구해야 하기때문에 미리 퍼질 수 있는 좌표를 큐에 넣어놓고 그 큐 안에서만 BFS를 돌려야한다. 이렇게 풀지 않을 경우 반례는 다음과 같다.

10 1 1
1 0 0 0 0 0 0 0 0 1