[C++] 백준 알고리즘 7569번 (토마토)

문제

---

이번에 다뤄볼 문제는 7569번 문제 '토마토'입니다.

토마토 문제에서 연습해야하는 key-point는 BFS입니다.

 

BFS는 너비 우선 탐색을 뜻하는데요.

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

이 문제는 7576번(토마토) 문제에서 살짝 응용 된 문제입니다. 

기존에서는 x,y에 의한 방향 이동만 존재했다면
이 문제에서는 z축 방향의 이동을 생각해 주면 됩니다.
그 외 문제를 푸는 방식은 7576번과 같습니다.

백준 알고리즘 7576번 (토마토)

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int map[101][101][101];
int visited[101][101][101] = { 0 };
 
int q[1000000][3];
int front = 0, rear = 0;
 
 
int dirX[6] = { -1,1,0,0, 0, 0 };
int dirY[6] = { 0,0,1,-1, 0, 0 };
int dirZ[6] = { 0,0,0, 0, 1, -1};
 
int main() {
 
    int m, n, h;
    int max = 0;
    int flag = 0;
    int check = 0;
 
    cin >> m >> n >> h;
 
    for (int k = 0; k < h; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> map[i][j][k];
 
                if (map[i][j][k] == 0) check = 1;
                if (map[i][j][k] == 1) {
                    q[rear][0] = i;
                    q[rear][1] = j;
                    q[rear++][2] = k;
                    visited[i][j][k] = 1;
                }
            }
        }
    }
    if (check == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    else {
        int x, y, z, xx, yy, zz;
 
        while (front != rear) {
            x = q[front][0]; y = q[front][1]; z = q[front++][2];
 
 
            for (int k = 0; k < 6; k++) {
                xx = x + dirX[k]; yy = y + dirY[k]; zz = z + dirZ[k];
 
                if (xx<0 || yy<0 || zz<0 || xx >= n || yy >= m || zz >= h || map[xx][yy][zz] != 0) continue;
                if (visited[xx][yy][zz] == 0 || visited[xx][yy][zz] > visited[x][y][zz] + 1) {
                    q[rear][0] = xx; q[rear][1] = yy; q[rear++][2] = zz;
                    map[xx][yy][zz] = 1;
                    visited[xx][yy][zz] = visited[x][y][z] + 1;
                }
            }
 
        }
 
 
        for (int k = 0; k < h; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (visited[i][j][k]>max) max = visited[i][j][k];
                    if (map[i][j][k] == 0) flag = 1;
                }
            }
        }
         
 
 
        if (flag == 0) cout << max - 1 << endl;
        if (flag == 1) cout << -1 << endl;
 
        return 0;
    }
 
}