BOJ 7569 토마토

문제

주의할 점

• 가능한 깊이(depth) 까지 최대한 내려간 것을 골라야함. (지난 일 수)

  사과가 모두 익는 경우는 BFS 탐색을 마칠 때임.
  (큐 안에는 안익은 사과만 들어간다)

• 문제에서 최소 일 수를 구하라고 한다.
  BFS를 사용할 때 방문한 곳은 다시 방문하지 않으므로 이미 경로가 최소가 된다.
  따라서 따로 최소를 구하려고 삽질할 필요가 없다.
  나는 생각이 짧아서 최소를 구하려고 했다. 덕분에 긴 시간동안 삽질했다 ^^
  최솟값 찾으라 했더니 최대값을 찾고 있다고 거부감 가지지 말것
  DP만 풀었더니 최솟값 찾는데만 혈안이었다. (min 사용해 해결하려고 함)

코드

// 2021.10.01 14:03:46
// 7569 https://boj.kr/7569
#include <bits/stdc++.h>
using namespace std;

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

int box[101][101][101];
int n, m, h;

class Node
{
public:
    int z, y, x, day;

    void ripe()
    {
        box[z][y][x] = 1;
    }

    bool isValid()
    {
        return this->z >= 0 && this->z < h && this->y >= 0 && this->y < n && this->x >= 0 && this->x < m;
    }
};


int bfs(vector<Node> &startNodes)
{
    queue<Node> q;
    for (auto &node : startNodes)
    {
        q.push(node);
    }

    int day = 0;
    while (!q.empty())
    {
        Node cur = q.front();
        q.pop();
        day = max(day, cur.day);

        for (int next = 0; next < 6; next++)
        {
            Node nextNode = Node({cur.z + dz[next], cur.y + dy[next], cur.x + dx[next], cur.day + 1});
            if (nextNode.isValid() && box[nextNode.z][nextNode.y][nextNode.x] == 0)
            {
                q.push(nextNode);
                nextNode.ripe();
            }
        }
    }

    return day;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> m >> n >> h;

    vector<Node> startNodes;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < m; k++)
            {
                cin >> box[i][j][k];
                if (box[i][j][k] == 1)
                {
                    startNodes.push_back(Node({i, j, k, 0}));
                }
            }
        }
    }

    int answer = bfs(startNodes);

    for (int i = 0; i < h; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < m; k++)
                if (box[i][j][k] == 0)
                {
                    cout << -1;
                    return 0;
                }
    cout << answer;
}

결과