반응형
문제 링크 : https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net

>풀이
BFS를 사용합니다. 유사문제 : https://minocode.tistory.com/28
백준 7576 (토마토) / C++
문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤..
minocode.tistory.com
위 문제에서 한 차원? 축? 이 하나 늘어난건데, 똑같이 하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef struct {
int x, y, z;
int cnt;
} types;
int M, N, H; //가로 세로 높이
int box[101][101][101];
bool visited[101][101][101];
int moveX[6] = {1, -1, 0, 0, 0, 0};
int moveY[6] = {0, 0, 1, -1, 0, 0};
int moveZ[6] = {0, 0, 0, 0, 1, -1};
queue<types> bfs;
int main(void) {
int cnt = 0;
scanf("%d %d %d", &M, &N, &H);
for (int k = 0; k < H; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
scanf("%d", &box[i][j][k]);
if (box[i][j][k] == 1) {
bfs.push({i, j, k, 0});
visited[i][j][k] = true;
}
else if (box[i][j][k] == -1)
visited[i][j][k] = true;
}
if (bfs.empty()) {
printf("-1");
return 0;
}
while (!bfs.empty()) {
auto a = bfs.front();
bfs.pop();
cnt = max(cnt, a.cnt);
for (int i = 0; i < 6; i++) {
int nx = a.x + moveX[i];
int ny = a.y + moveY[i];
int nz = a.z + moveZ[i];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < N && ny < M && nz < H && !visited[nx][ny][nz]) {
bfs.push({nx, ny, nz, a.cnt + 1});
visited[nx][ny][nz] = true;
}
}
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
for(int k = 0; k < H; k++)
if (!visited[i][j][k]) {
printf("-1");
return 0;
}
printf("%d", cnt);
return 0;
}
(개발 환경 : vscode)
반응형
'알고리즘 (백준) > BOJ 길라잡이 (1)' 카테고리의 다른 글
백준 2583 (영역 구하기) / C++ (0) | 2020.11.02 |
---|---|
백준 2636 (치즈) / C++ (0) | 2020.10.14 |
백준 7576 (토마토) / C++ (0) | 2020.10.07 |
백준 2206 (벽 부수고 이동하기) / C++ (0) | 2020.08.25 |
백준 1149 (RGB거리) / C++ (0) | 2020.08.24 |