문제
"맞았습니다" 코드
#include <bits/stdc++.h>
using namespace std;
// 7569 토마토
int n, m, h; // 행, 열, 높이,
int target; // 익혀야할 개수
int box[102][102][102];
int vis[102][102][102];
int dx[] = {0, 0, 0, 0, -1, 1}; // 높이
int dy[] = {0, 1, 0, -1, 0, 0}; // 행
int dz[] = {-1, 0, 1, 0, 0, 0}; // 열
queue<tuple<int, int, int>> qu; // {h좌표, x좌표, y좌표}
void initarr(){
for(int i = 0; i < 102; i++) { // 높이
for (int j = 0; j < 102; j++) { // 행
fill(vis[i][j], vis[i][j]+102, -1);
}
}
}
bool checkrange(int i, int j, int k){ // 높이, 행, 열 -> 유효범위 체크
return (i > 0 && i <= h && j > 0 && j <= n && k > 0 && k <= m);
}
int bfs(){
int day = 0;
while(!qu.empty()){
int curx = get<0>(qu.front()); // 높이
int cury = get<1>(qu.front()); // 행
int curz = get<2>(qu.front()); // 열
qu.pop();
for(int i = 0; i < 6; i++){ // 6방향 체크한다
int nx = curx + dx[i];
int ny = cury + dy[i];
int nz = curz + dz[i];
// 유효범위, 안익은 토마토(방문배열-1)인지, 토마토가 있는지 여부.
if(!checkrange(nx, ny, nz) || vis[nx][ny][nz] != -1 || box[nx][ny][nz] == -1) continue;
vis[nx][ny][nz] = vis[curx][cury][curz] + 1; // 현재날짜 +1
day = max(day, vis[nx][ny][nz]);
qu.push(make_tuple(nx,ny,nz));
target--; // 익혔다
}
}
return day;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n >> h; // 열,행,높이 순서
initarr(); // 방문배열에는 익은 날짜를 저장할 것이므로 전부 -1로 초기화
for(int i = 1; i <= h; i++){ // 높이
for(int j = 1; j <= n; j++){ // 행
for(int k = 1; k <= m; k++){ // 열
cin >> box[i][j][k];
if(box[i][j][k] == 0) {
target++; // 익혀야 할 토마토(0) 개수 세기
vis[i][j][k] = -1; // 방문 타겟
}
if(box[i][j][k] == 1) { // 이미 익은 토마토(1) 는 시작점이 된다.
vis[i][j][k] = 1;
qu.push(make_tuple(i, j, k));
}
}
}
}
if(target == 0) cout << 0; // 익혀야할 것이 없다
else{
int day = bfs();
if(target == 0) cout << day-1;
else cout << -1;
}
return 0;
}
리뷰
7576 토마토는 2차원이었는데, 7569 토마토는 3차원이다.
익은 토마토는 동서남북을 익히니까 익은 토마토 좌표를 모두 큐에 넣는다.
dx, dy, dz를 이용해 상하좌우 위아래 모두 확인한다.
728x90
'알고리즘 > 백준' 카테고리의 다른 글
상범빌딩 백준 6593번 c++ (0) | 2021.12.08 |
---|---|
나무 자르기 백준 2805 c++ (0) | 2021.12.06 |
숨바꼭질3 백준 13549 c++ (0) | 2021.12.05 |
적록색약 백준 10026 c++ (0) | 2021.12.03 |
유기농 배추 백준 1012 c++ (0) | 2021.12.03 |