[백준 C++] 7569 토마토 - 너비우선탐색

7569번: 토마토

cpp

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

typedef tuple<int, int, int> Coord;

int Box[100][100][100];
int Day[100][100][100];

int M, N, H;
int DX[6] = { -1, 1, 0, 0, 0, 0 }; // Left, Right
int DY[6] = { 0, 0, -1, 1, 0, 0 }; // Top, Bottom
int DZ[6] = { 0, 0, 0, 0, -1, 1 }; // Down, Up

queue<Coord> SearchQueue;

int CountDays()
{
‌int MaxDay = 0;
‌
‌// Binary First Search
‌while (!SearchQueue.empty())
‌{
‌‌int X = get<0>(SearchQueue.front());
‌‌int Y = get<1>(SearchQueue.front());
‌‌int Z = get<2>(SearchQueue.front());
‌‌SearchQueue.pop();

‌‌if (Box[Z][Y][X] == -1)
‌‌{
‌‌‌continue;
‌‌}

‌‌Box[Z][Y][X] = -1;
‌‌for (int i = 0; i < 6; ++i)
‌‌{
‌‌‌int NX = X + DX[i];
‌‌‌int NY = Y + DY[i];
‌‌‌int NZ = Z + DZ[i];

‌‌‌if (NX < 0 || NX > M - 1
‌‌‌‌|| NY < 0 || NY > N - 1
‌‌‌‌|| NZ < 0 || NZ > H - 1
‌‌‌‌|| Box[NZ][NY][NX] == -1)
‌‌‌{
‌‌‌‌continue;
‌‌‌}

‌‌‌if (Box[NZ][NY][NX] == 0)
‌‌‌{
‌‌‌‌Box[NZ][NY][NX] = 1;

‌‌‌‌int NewDay = Day[Z][Y][X] + 1;
‌‌‌‌Day[NZ][NY][NX] = NewDay;
‌‌‌‌if (NewDay > MaxDay)
‌‌‌‌{
‌‌‌‌‌MaxDay = NewDay;
‌‌‌‌}
‌‌‌}

‌‌‌SearchQueue.emplace(NX, NY, NZ);
‌‌}
‌}

‌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)
‌‌‌‌{
‌‌‌‌‌return -1;
‌‌‌‌}
‌‌‌}
‌‌}
‌}

‌return MaxDay;
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL); cout.tie(NULL);

‌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 >> Box[i][j][k];
‌‌‌‌if (Box[i][j][k] == 1)
‌‌‌‌{
‌‌‌‌‌SearchQueue.emplace(k, j, i);
‌‌‌‌}
‌‌‌}
‌‌}
‌}

‌cout << CountDays();
}

---

 

3차원 공간에서 너비 우선 탐색을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 입력 받은 토마토 정보 box 배열에 저장 - 처음부터 익은 토마토는 BFS 큐에 추가

2. 각 토마토가 몇번째 날에 익었는지 정보를 담는 day 배열 모두 0 값으로 초기화

3. 큐에 담긴 토마토부터 너비 우선 탐색 시작

4. 익지 않은 인접 토마토에 현재 토마토 날짜 + 1 날짜 값 저장 - 이 때 현재까지 증가된 날짜 중 최대값은 따로 저장

5. 탐색을 마친 후, 저장해놓은 날짜 최대값 출력 - 예외처리: 익지 않은 토마토가 존재하면 -1 출력