득이공간
[백준 C++] 7569 토마토 - 너비우선탐색 본문
#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 출력
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 9019 DSLR - 너비우선탐색 (0) | 2024.02.18 |
---|---|
[백준 C++] 7662 이중 우선순위 큐 - 우선순위큐 (0) | 2024.02.18 |
[백준 C++] 5430 AC - 덱 (0) | 2024.02.17 |
[백준 C++] 1107 리모컨 - 브루트포스 (0) | 2024.02.17 |
[백준 C++] 20529 가장 가까운 세 사람의 심리적 거리 - 브루트포스 (0) | 2024.02.17 |