[백준] 7569 토마토 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/7569

7569번: 토마토

 전형적인 bfs 문제입니다. 3차원 배열이 싫다하시는 분들은 7576의 토마토 문제를 추천 드립니다. 두 문제 모두 같은 방법으로 풀 수 있습니다. 

---

2. 풀이 과정

• 문제 해결의 흐름
  
  1. 입력 받은 배열에 관해 토마토가 익은 상태(1)라면 큐에 저장하자.
  2. 큐에 저장된 값 주위(총 6방향)를 탐색하며 안 익은 토마토(0)가 있다면 익은 토마토로 바꾸고 방문처리하자.
  3. 조건에 따라 다른 결과값은 제시하자
• 나의 코드 

//
// Created by 태윤맥북 on 4/15/24.
// 2. 결과값은 5015번 풀었을 때처럼 처리하면 될 거 같다.
//

#include <iostream>
#include <queue>

using namespace std;

// 토마토의 좌표값
struct coordinate {
    int x;
    int y;
    int z;
};


int M, N, H, tomato; // M : 가로 칸 수, N : 세로 칸 수, H : 상자의 높이, tomato : 토마토 개별 정보
int tomato_box[101][101][101]; // 입력 받을 배열 설정
int visited[101][101][101] = {}; // 전부 0으로 초기화
queue<coordinate> q;

int day = 0; // 토마토 익는 날 계산

// 익은 토마토 주위의 6방향 표시
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 bfs() {
    while(!q.empty()) {
        // 익은 토마토 위치
        int now_x = q.front().x;
        int now_y = q.front().y;
        int now_z = q.front().z;
        q.pop();

        // 익은 토마토 주위로 6방향 탐색
        for (int i = 0; i < 6; i++) {
            int nx = now_x + dx[i];
            int ny = now_y + dy[i];
            int nz = now_z + dz[i];

            // 범위 밖이면 continue
            if (nx < 0 or nx >= M or ny < 0 or ny >= N or nz < 0 or nz >= H) continue;

            // 안 익은 토마토가 있고 방문한 적이 없으면 익은 토마토로 바꾸고 queue에 넣어주기
            if (tomato_box[nz][ny][nx] == 0 and visited[nz][ny][nx] == -1) {
                coordinate add_tomato;
                tomato_box[nz][ny][nx] = 1;
                add_tomato.x = nx;
                add_tomato.y = ny;
                add_tomato.z = nz;
                q.push(add_tomato);
                // 5014번 풀었을 떄와 같은 방법!
                visited[nz][ny][nx] = visited[now_z][now_y][now_x] + 1;
            }
        }
    }

    for (int h = 0; h < H; h++) {
        for (int n = 0; n < N; n++) {
            for (int m = 0; m < M; m++) {
                if (tomato_box[h][n][m] == 0) return -1; // 토마토가 모두 익지 못하는 경우
                day = max(day, visited[h][n][m]);
            }
        }
    }


    return day;
}

int main() {
    cin >> M >> N >> H;
    fill_n(&tomato_box[0][0][0], 101 * 101 * 101, -1);  // 아직 입력 받지 않았기에 토마토 없음!

    // 토마토 입력 받기
    for (int h = 0; h < H; h++) {
        for (int n = 0; n < N; n++) {
            for (int m = 0; m < M; m++) {
                cin >> tomato;
                tomato_box[h][n][m] = tomato;

                coordinate tomato_coord;
                tomato_coord.x = m;
                tomato_coord.y = n;
                tomato_coord.z = h;

                if (tomato == 1) {  // 익은 토마토 정보는 queue에 저장하기
                    q.push(tomato_coord);
                }
                if (tomato == 0) visited[h][n][m] = -1;	// 토마토가 전부 익었을 경우를 대비해서 
            }
        }
    }

    cout << bfs();

    return 0;
}

 

• 이 문제를 통해 얻어 갈 수 있는 것들 
  • ⭐️ 특정 좌표값 주위를 반복문을 통해 탐색할 때 dx[6], dy[6], dz[6]와 같은 배열을 이용하곤 한다. 자주 이용되므로 코드 스니펫에 등록하도록 하자.
  •  큐에 좌표값과 같이 여러 값을 포함하는 변수를 저장할 때는 구조체를 사용해보자.
  • ⭐️⭐️⭐️ bfs를 처리하는데 걸린 일자, 횟수 등을 물어보는 문제가 종종 있다. 이의 경우 방문 처리를 하는 배열을 0으로 초기화해 선언한 후 너비를 넓힐 때마다, 즉 방문처리의 범위를 넓힐 때마다 1을 더해주는 방식으로 결과값을 구하자. 

 

---

3. 후기 

 전형적인 bfs 문제였다. 원래 7576 문제를 풀기로 되어있었지만 문제 번호를 헷갈려 3차원 배열을 풀어벼렸다 ㅠ.. 방문 처리 배열을 통해 bfs를 처리하는 데 걸리는 일자를 구하는 방식을 이해하는데 시간을 꽤 썼는데 이해하고 나니 bfs라는 문제의 개념을 관통하는 듯하다!