[BOJ] 백준 7569 토마토 c++ 코드 / 풀이

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

7569번: 토마토

 

 

 

문제설명

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

7576번: 토마토

이 문제의 3차원 버전?

익은 토마토와, 익지않은 토마토가 들어있는 위치, 비어있는 칸의 위치가 주어질 때 

익은 토마토의 위, 아래, 앞, 뒤, 좌, 우에 위치한 익지 않은 토마토는 다음 날 익게 됨

이럴 때 보관된 모든 토마토가 익는 최소 일 수를 출력

 

문제풀이

1. 익은 토마토를 모두 큐에 넣고 BFS 돌리기
2. 입력받을때 아예 1인걸 큐에 넣어버린후에
3. 큐가 빌때까지 BFS실행, 이때 익은 토마토를 0으로 하고 안익은 토마토의 dist을 +1해주면서 재면됨
4. 만약에 BFS 끝났는데 안익은 토마토 있으면 -1 출력 다 익었다면 배열의 max값 출력

 

 

코드설명

익은 토마토의 위치를 큐에 넣고 방문 체크

익지 않은 토마토의 dist 배열 값을 -1로 설정하여 아직 방문하지 않았음을 표시

큐가 빌 때까지 BFS를 실행하며 큐에서 토마토의 위치를 하나씩 꺼내서 해당 토마토의 상하좌우와 위아래 층을 확인

만약 인접한 토마토가 익지 않았다면(dist 값이 -1), 현재 토마토의 dist 값에 1을 더하여 인접한 토마토의 dist 값을 갱신

이 값은 시작점으로부터의 거리(일수)

각 방향을 확인할 때, 상자의 범위를 벗어나지 않는지, 이미 방문했는지(즉, dist 값이 0 이상) 확인

BFS 실행이 끝나면, dist 배열을 검사하여 모든 토마토가 익었는지 확인

만약 익지 않은 토마토가 있다면(즉, dist 값이 -1인 칸이 있다면) -1을 출력

모든 토마토가 익었다면, dist 배열 중 최댓값을 찾아 출력

 

코드

#include <bits/stdc++.h>
#define PRESET ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int arr[101][101][101];
int dist[101][101][101];
int main(){
    PRESET;

    /*
    1. 익은 토마토를 모두 큐에 넣고 BFS 돌리기
    2. 입력받을때 아예 1인걸 큐에 넣어버린후에
    3. 큐가 빌때까지 BFS실행, 이때 익은 토마토를 0으로 하고 안익은 토마토의 dist을 +1해주면서 재면됨
    4. 만약에 BFS 끝났는데 안익은 토마토 있으면 -1 출력 다 익었다면 배열의 max값 출력
    
    */

    queue<tuple<int, int, int>> q;
    int N, M, H;

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1}; //하, 우, 상, 좌1
    int dz[4] = {-1, 1};
    int max_cnt = 0, cnt = 0;// max size

    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 >> arr[k][i][j];
                if(arr[k][i][j] == 1) q.push({k,i,j});
                if(arr[k][i][j] == 0) dist[k][i][j] = -1;
            }
        }
    }
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(int i = 0; i < 4; i++){         
            int nx = get<1>(cur) + dx[i];
            int ny = get<2>(cur) + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if(dist[get<0>(cur)][nx][ny] >= 0) continue;

            dist[get<0>(cur)][nx][ny] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
            q.push({get<0>(cur),nx,ny});
        }
        for(int i = 0; i < 2; i++){
            int nz = get<0>(cur) + dz[i];
            
            if(nz < 0 || nz >= H) continue;
            if(dist[nz][get<1>(cur)][get<2>(cur)] >= 0) continue;

            dist[nz][get<1>(cur)][get<2>(cur)] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
            q.push({nz, get<1>(cur), get<2>(cur)});
        }
    }

for(int k = 0; k < H; k++){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(dist[k][i][j] == -1) {
                cout << -1;
                return 0;
            }
            else{
                max_cnt = max(max_cnt, dist[k][i][j]);
            }
        }
    }
}
    cout << max_cnt;
    
}