[Algorithm: BFS/DFS] 백준 7569 토마토 (C++)

문제

입력 & 출력

풀이 방법

이 문제를 풀면서 챌린지 요소가 두가지 였는데, 첫번째는 최소 일 수는 어떻게 계산할 것인가였고 두번째는 만일 익지 않은 토마토가 있다면 어떻게 확인할 것인가였다.

 

두번째에 대한 답안은 그래프 전체 탐색 알고리즘을 돌렸음에도 토마토가 익지 않은게 있다면 바로 -1 을 출력하고 함수를 끝내버리면 됨이다.

최소 일수를 반영하는게 어려웠는데 그 이유는 시작점이 하나가 아니라 첫 날에 익어있는 모든 토마토가 시작점이 되기 때문이다. 

 

어떤 토마토는 4일째에 익었고 어떤 토마토는 5일째에 익을 수도 있다. 그러면 토마토가 익는데 걸리는 최소 일수는 5일이다. 그래서 max 함수를 통해 익는데 가장 오래 걸리는 토마토의 일수를 알아야한다.  

 

여기서 나는 이런 방법을 사용했다.

1. 익는데 걸리는 일수를 토마토 위치에 저장해놓는다.

2. 전체 일 수 중에 최댓값을 프린트한다.

 

코드

#include<iostream>
#include <queue>

#define MAX 100
using namespace std;

int dx[6] = {-1, 1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {0, 0, 0, 0, -1, 1};
int days[MAX][MAX][MAX] = {{0,}};
bool visited[MAX][MAX][MAX] = {false,};
int tomatoes[MAX][MAX][MAX];
int M, N, H;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int cnt = 0;
    cin >> M >> N >> H;
    queue<pair<pair<int, int>, int>> q; // x,y,z가 필요하기 때문에 pair가 두 번 필요하다.
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                cin >> tomatoes[k][j][i];
                if (tomatoes[k][j][i] == 1) {
                    visited[k][j][i] = true;
                    q.push({{k, j}, i});
                    // i는 z(높이니까), j는 y, k는 x
                } else if (tomatoes[k][j][i] == 0 && visited[k][j][i] == false)
                    visited[k][j][i] = false;
            }
        }
    }
    while (!q.empty()) {
        int nx = q.front().first.first;
        int ny = q.front().first.second;
        int nz = q.front().second;
        visited[nx][ny][nz] = true;
        q.pop();
        for (int i = 0; i < 6; i++) {
            int ix = nx + dx[i];
            int iy = ny + dy[i];
            int iz = nz + dz[i];
            if (ix >= 0 && ix < M && iy >= 0 && iy < N && iz >= 0 && iz < H && tomatoes[ix][iy][iz] == 0 && visited[ix][iy][iz] == false) {
                //무한루프에 빠지지 않도록
                visited[ix][iy][iz] = true;
                q.push({{ix,iy},iz});
                days[ix][iy][iz] = days[nx][ny][nz] + 1;
            }
        }
    }
    for (int i = 0; i < H; i++){
        for(int j = 0; j< N;j++){
            for(int k = 0;k<M;k++){
                if(tomatoes[k][j][i] == -1 ) continue;
                if(tomatoes[k][j][i] == 0 && visited[k][j][i] == false){
                    cout<<"-1";
                    return 0;
                }
                cnt = max(cnt, days[k][j][i]);
            }
        }
    }
    cout<< cnt;
    return 0;
}

특이점

원래 bfs 함수를 따로 빼서 그래프 탐색을 구현하는데 여기서는 !시작점이 여러개! 이기 때문에 1일 경우 메인함수 안에 있는 큐에 push 해주고 다 입력을 받고 난 후 메인 함수 안에서 탐색을 진행했다.