[백준] C++ 7569번:토마토!

<초기 코드>

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x, y, z;
    cin >> x >> y >> z;

    vector<vector<vector<int>>> v (z, vector<vector<int>>(y, vector<int>(x, -1)));  
    vector<vector<vector<int>>> vis (z, vector<vector<int>>(y, vector<int>(x, 0)));  
    
    //1: 익은토마토, 0: 익지 않은 토마토, -1: 토마토 없음
    for (int zz = 0; zz < z; zz++){
        for (int yy = 0; yy < y; yy++) {
            for (int xx = 0; xx < x; xx++) {
                cin >> v[zz][yy][xx];
            }
        }
    }

    int cnt = 0;

    // 기본 BFS에 탐색 기준 영역의 z 축 위, 아래의 해당 x, y 좌표만 방문 표시 및 push 만 추가하면 된다.
    queue<tuple<int, int, int>> q;
    for (int zz = 0; zz < z; zz++){
        for (int yy = 0; yy < y; yy++) {
            for (int xx = 0; xx < x; xx++) {
                if (v[zz][yy][xx] == 1 && vis[zz][yy][xx] == 0) {
                    q.push({zz, yy, xx});
                    vis[zz][yy][xx] = 1;
                    while (!q.empty()){
                        auto cur = q.front();
                        q.pop();
                        cnt++;
                        for(int i = 0; i < 6; i++) {
                            int zzz = get<0>(cur) + dz[i];
                            int yyy = get<1>(cur) + dy[i];
                            int xxx = get<2>(cur) + dx[i];
                            if (zzz > -1 && zzz < z && yyy > -1 && yyy < y && xxx > -1 && xxx < x && v[zzz][yyy][xxx] != -1 && vis[zzz][yyy][xxx] == 0) {
                                q.push({zzz, yyy, xxx});
                                v[zzz][yyy][xxx] = 1;
                                vis[zzz][yyy][xxx] = 1;
                            }
                        }
                    }
                }
            }
        }
    }

    for(auto zz : v) {
        for(auto yy : zz) {
            for (auto xx : yy) {
                cout << xx << " ";
                if (xx == 0){
                    //cout << "-1";
                    //eturn 0;
                }
            }
            cout << "\n";
        }
        cout << "\n";
    }

    // 토마토가 모두 익지 않았을땐 -1을 출력
    cout << cnt;

    return 0;
}

 

일 수가 제대로 안세어지길래 다시 생각해보니 위와 같은 식으로 하면 하나의 익은 토마토를 발견하고 그 주위에 채우기를 먼저 하는 코드이다. 하지만 문제에서는 일 수를 카운트하라고 하였기 때문에 처음에 익은 토마토(1)을 먼저 q에 넣고 돌려야 나온다. 또한 1일차에 넣은 토마토들이 끝나면 카운트 하는 방법도 생각해야한다. 

 

vis 벡터가 없어도 되어서 삭제했다.

 

핵심 요소

1. 처음엔 익은 토마토(1)만 q에 모두 넣는다.

2. BFS에 y축으로 추가로 위, 아래만 넣는다.

3. v 벡터에 이전 영역의 방문값 + 1 을 해서 몇일차에 익은건지 표시 (vis 벡터가 필요없는 이유)

 

<정답>

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x, y, z;
    cin >> x >> y >> z;

    vector<vector<vector<int>>> v (z, vector<vector<int>>(y, vector<int>(x, -1)));  
    
    //1: 익은토마토, 0: 익지 않은 토마토, -1: 토마토 없음
    for (int zz = 0; zz < z; zz++){
        for (int yy = 0; yy < y; yy++) {
            for (int xx = 0; xx < x; xx++) {
                cin >> v[zz][yy][xx];
            }
        }
    }

    // 기본 BFS에 탐색 기준 영역의 z 축 위, 아래의 해당 x, y 좌표만 추가하면 된다.
    queue<tuple<int, int, int>> q;
    for (int zz = 0; zz < z; zz++){
        for (int yy = 0; yy < y; yy++) {
            for (int xx = 0; xx < x; xx++) {
                // 처음에 한번 익은 토마토들만 넣기
                if (v[zz][yy][xx] == 1 ) {
                    q.push({zz, yy, xx});
                }
            }
        }
    }
    
    int cnt = 0; 
    
    while (!q.empty()){
        auto cur = q.front();
        q.pop();
        for(int i = 0; i < 6; i++) {
        int zzz = get<0>(cur) + dz[i];
        int yyy = get<1>(cur) + dy[i];
        int xxx = get<2>(cur) + dx[i];
            if (zzz > -1 && zzz < z && yyy > -1 && yyy < y && xxx > -1 && xxx < x && v[zzz][yyy][xxx] == 0) { // 안익은 토마토만 push
                q.push({zzz, yyy, xxx});
                // 이전 영역의 방문 값 + 1 해서 몇일차에 익은건지 표시
                v[zzz][yyy][xxx] = v[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
            }
        }
    }

    for(auto zz : v) {
        for(auto yy : zz) {
            for (auto xx : yy) {
                if(cnt < xx ) {
                    cnt = xx;
                }
                if (xx == 0){
                    cout << "-1";
                    return 0;
                }
            }
        }
    }

    cout << cnt - 1 ;

    return 0;
}