[백준][C++] 7569번: 토마토 <241>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1. 생각의 흐름

이번문제는 Queue를 얼마나 잘 활용하는지가 핵심이다.

 

보통 BFS문제는 (!Q.size)동안 반복문을 돌게 된다.

문제는 이렇게 한번에 다 BFS탐색을 돌면, 하루안에 모든 과일이 익은것 처럼 코드가 작동한다.

 

우리는 하루마다 이미 익어있는 토마토에 인접한 토마토만 익도록 만들어야 한다.

따라서 BFS도 하루 단위로 동작해야 한다. 그래야 총 몇일이 소모됬는지 확인할 수 있다.

 

이를 위해서는 Queue의 사이즈를 이용해야 한다.

 

문제의 input을 보자.

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

맨처음 Queue에 익은 토마토만 삽입한 후의 상태는 다음과 같다.

 

Queue: [{1, 3, 0}, {1, 4, 0}, {2, 3, 0}, {2, 4, 0}]

이때 큐의 사이즈는 4가 된다. 따라서 4만큼 반복문들 돌면서 해당 위치들의 인근 지점들을 확인한다.

이를 코드로 보면 다음과 같다.

while(!Q.empty()) {
    int q_size = Q.size(); // Q의 사이즈 만큼 반복할것, 위 예시에서는 4가됨
    day++;

    for(int size = 0; size < q_size; size++) { // 총 4번 꺼냄
        Position nowPosition = Q.front();
        Q.pop();

        for (int i = 0; i < 6; i++) {
            int nextX = nowPosition.x + dx[i];
            int nextY = nowPosition.y + dy[i];
            int nextH = nowPosition.h + dh[i];

            if (nextX < 0 || nextY < 0 || nextH < 0 || nextX >= N || nextY >= M || nextH >= H) continue;

            if (box[nextX][nextY][nextH] == 0) {
                box[nextX][nextY][nextH] = 1;
                Q.push(Position(nextX, nextY, nextH));
            }
        }
    }

}

큐의 사이즈만큼 반복하여 꺼내는데, 이때 [{1, 3, 0}, {1, 4, 0}, {2, 3, 0}, {2, 4, 0}] 가 꺼내진다.

 

위 4개의 지점을 확인하면서 Q에는 다시 위치들이 추가될 수 있다.

하지만 아직 Q가 비어있는것은 아니기 때문에 day++을 진행한후 다시 반복하게 된다.

 

2. 나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 101

int M, N, H;
int day;
int box[MAX][MAX][MAX];

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

class Position{
public:
    int x;
    int y;
    int h;
public:
    Position(int x, int y, int h) : x(x), y(y), h(h) {}
};

void isRipe() {
    for(int h = 0; h < H; h++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(box[i][j][h] == 0) {
                    cout << -1;
                    exit(0);
                }
            }
        }
    }
}

queue<Position> Q;

void BFS() {

    while(!Q.empty()) {
        int q_size = Q.size();
        day++;

        for(int size = 0; size < q_size; size++) {
            Position nowPosition = Q.front();
            Q.pop();

            for (int i = 0; i < 6; i++) {
                int nextX = nowPosition.x + dx[i];
                int nextY = nowPosition.y + dy[i];
                int nextH = nowPosition.h + dh[i];

                if (nextX < 0 || nextY < 0 || nextH < 0 || nextX >= N || nextY >= M || nextH >= H) continue;

                if (box[nextX][nextY][nextH] == 0) {
                    box[nextX][nextY][nextH] = 1;
                    Q.push(Position(nextX, nextY, nextH));
                }
            }
        }
    }
    isRipe();
}

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

    cin >> M >> N >> H;

    for(int h = 0; h < H; h++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                cin >> box[i][j][h];
            }
        }
    }

    for(int h = 0; h < H; h++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(box[i][j][h] == 1) {
                    Q.push(Position(i, j, h));
                }
            }
        }
    }

    BFS();

    cout << day - 1;

    return 0;
}