[BOJ/7569토마토2] c++ / BFS

문제

상자 안에 있는 토마토가 모두 익을 때까지의 최소 날짜를 구하는 문제

-익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없는 칸은 -1로 표시됨

생각

7576번 토마토 문제의 업그레이드 문제임

3차원배열 사용해야겠구나 생각함

4칸은 원래 하던대로 탐색하면 될 것이고, 위, 아래를 어떤식으로 탐색하면 좋을지 생각했음

원래 BFS 풀던 코드에 반복문만 하나 추가해줬음 ( nz 확인 )

 

문제풀이

1.vis배열을 -1로 초기화시킴

2. board에서 토마토가 들어있는 칸을 큐에 모두 집어넣음

-동시에 토마토가 익을 수 있음

2. 1번 과정에서 익지 않은 토마토 칸이 나오면 0 표시해줌 ( 나중에 토마토가 모두 익었는지 확인하기 위함 )

익은 토마토가 나오면 1 표시 해줌

3. 반복문 사용해서 익은 토마토 기준으로 상하 좌우, 위 아래에 익지 않은 토마토가 있는지 확인 ( 코드에선 day칸이 0인지 확인했음 )

4. 안 익은 토마토의 day칸에는 기준이 되었던 토마토의 day칸 값에서 1을 더해준 값을 저장함

5. day 칸에 0이 있으면 토마토가 익지 않은 것임 \ 다 익었으면 day칸에서 최댓값을 찾아 출력하면 됨

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int board[101][101][101];
int vis[101][101][101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dz[2] = {1, -1};
int N, M, H, result=0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> M >> N >> H;
    for ( int i = 0; i < H; i++ )
        for ( int j = 0; j < N; j++ )
            for ( int k = 0; k < M; k++ ) 
                cin >> board[i][j][k];

    queue<tuple<int, int, int>> Q; // tuple 은 세쌍값을 묶음
    fill(&vis[0][0][0], &vis[H][N][M], -1 );

    for ( int i = 0; i < H; i++ )
        for ( int j = 0; j < N; j++ )
            for ( int k = 0; k < M; k++ ) {
                if ( board[i][j][k] == 1 ) {
                    vis[i][j][k] = 1;
                    Q.push({i, j, k});
                }
                else if ( board[i][j][k] == 0 ) {
                    vis[i][j][k] = 0;
                }
            }

    while (!Q.empty()) {
        tuple<int, int, int> cur = Q.front(); Q.pop();
    
        for ( int dir = 0; dir < 4; dir++ ) {
            int nz = get<0>(cur);
            int nx = get<1>(cur) + dx[dir];
            int ny = get<2>(cur) + dy[dir];
                    
            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( board[nz][nx][ny] != 0 || vis[nz][nx][ny] > 0 ) continue;
                    
            vis[nz][nx][ny] = vis[nz][get<1>(cur)][get<2>(cur)] + 1;
            Q.push({nz, nx, ny});
        }
        
        for ( int dir = 0; dir < 2; dir++ ) {
            int nz = get<0>(cur) + dz[dir];
            int nx = get<1>(cur);
            int ny = get<2>(cur);
            if ( nz >= H || nz < 0 ) continue;
            if ( board[nz][nx][ny] != 0 || vis[nz][nx][ny] > 0 ) continue;

            vis[nz][nx][ny] = vis[get<0>(cur)][nx][ny] + 1;
            Q.push({nz, nx, ny});
        }
    }


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

    cout << result-1;
}

필요

tuple 접근

get<index>(변수);