[알고리즘 문제] 백준 7569번 토마토

7569번: 토마토 (acmicpc.net)

7569번: 토마토

 

문제

 3차원 배열 그래프 상에서 토마토가 익는 시간을 측정하는 문제입니다.

 

아이디어

 BFS를 사용하는 몇 가지 방법이 있겠지만, 여기서는 가장 단순한 방법을 사용합니다.

 시간을 들여 직접 토마토를 익혀봅시다.

 

 1. 처음 익은 토마토의 리스트를 만듭니다. 정확히는 다음 시간에 주변에 영향을 줄 토마토들입니다.

 2. 익은 토마토의 주변에 안 익은 토마토, 즉 다음에 익을 토마토를 익히고 리스트로 만듭니다.

 3. 2번에서 만든 리스트로 다시 2번 과정을 반복합니다.

 4. 더 이상 다음에 익을 토마토가 없을 때 종료합니다.

 5. 상자를 확인해 안 익은 토마토가 있으면 실패로 -1을 출력합니다.

 

 예외적으로 시작 시 모든 토마토가 익었으면 0을 출력합니다.

코드

#include <iostream>
#include <cstring>
#include <tuple>
#include <list>
#include <functional>
using namespace std;

int box[102][102][102];
int H, M, N;
int answer = -1;

int xxx[] = { 1, -1, 0, 0, 0, 0 };
int yyy[] = { 0, 0, 1, -1, 0, 0 };
int zzz[] = { 0, 0, 0, 0, 1, -1 };

list<tuple<int, int, int>> *next_tomato, *cur_tomato;
list<tuple<int, int, int>> s1, s2;

void loop(function<void(int, int, int)> f) {
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= M; k++) {
                f(i, j, k);
            }
        }
    }
}

int main(void) {
    cin >> M >> N >> H;

    memset(box, -1, sizeof(int) * 102 * 102 * 102);
    loop([&] (int i, int j, int k) {
         cin >>  box[i][j][k];
    });

    // 익을 토마토가 없음
    bool theres_no_raw = true;
    loop([&] (int i, int j, int k) {
        if (box[i][j][k] == 0)
            theres_no_raw = false;
    });
    if (theres_no_raw) {
        cout << 0;
        return 0;
    }

    cur_tomato = &s1;
    next_tomato = &s2;
    loop([&] (int i, int j, int k) {
         if (box[i][j][k] == 1)
            cur_tomato->push_back(make_tuple(i, j, k));
    });

    while (cur_tomato->size() != 0) {
        answer++;

        for (auto tomato : *cur_tomato) {
            int x, y, z;
            tie(x, y, z) = tomato;

            for (int i = 0; i < 6; i++) {
                int xx = xxx[i], yy = yyy[i], zz = zzz[i];
                if (box[x + xx][y + yy][z + zz] == 0) {
                    box[x + xx][y + yy][z + zz] = 1;
                    next_tomato->push_back(make_tuple(x + xx, y + yy, z + zz));
                }
            }
        }

        cur_tomato->clear();
        auto temp = cur_tomato;
        cur_tomato = next_tomato;
        next_tomato = temp;
    }

    bool is_all_fri = true;
    loop([&] (int i, int j, int k) {
         if (box[i][j][k] == 0)
            is_all_fri = false;
    });


    if (is_all_fri) {
        cout << answer;
    }
    else
        cout << -1;
}

 

 토마토의 위치를 tuple로 관리합니다.

 한 번의 시행에서 현재 영향을 주는 토마토의 리스트, 다음에 영향을 주는 토마토의 리스트 두 개가 필요합니다.

 이때 리스트를 복사하면 비효율적이니 포인터를 사용해 두 개의 리스트를 스왑 하는 식으로 만들었습니다.

 

기타

 이번 문제처럼 다차원 배열을 여러 번 순회해야 할 경우 for 문을 중첩할 때 실수하기 쉽습니다.

 따라서 인덱스를 순회하는 함수를 만들어 관리하는 것이 간편합니다.

void loop(function<void(int, int)> f) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            f(i, j);
}

loop([] (int i, int j) {
     // do something
});