💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 7136KB Time 124ms Code Length 1350B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<stdio.h>
#include<queue>
using namespace std;
struct INFO {
int z, y, x;
int cnt;
};
int n, m, h;
int map[101][101][101];
int isThereRaw() {
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (map[i][j][k] == 0)
return 1;
}
}
}
return 0;
}
int main() {
scanf("%d %d %d", &m, &n, &h);
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
scanf(" %d", &map[i][j][k]);
}
}
}
queue<INFO> q;
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (map[i][j][k] == 1) q.push({ i,j,k,0 });
}
}
}
int result = -1;
int cnt_check = -1;
int dz[] = {0 , 0 , -1, 1 , 0, 0};
int dy[] = {-1, 1, 0 , 0 , 0 ,0 };
int dx[] = {0, 0 , 0 , 0 , -1, 1};
while (!q.empty()) {
INFO tmp = q.front(); q.pop();
if (cnt_check != tmp.cnt) {
cnt_check = tmp.cnt;
if (!isThereRaw()) {
result = tmp.cnt;
break;
}
}
for (int i = 0; i < 6; i++) {
int nz = tmp.z + dz[i];
int ny = tmp.y + dy[i];
int nx = tmp.x + dx[i];
if (nz >= h || ny >= n || nx >= m || nz < 0 || ny < 0 || nx < 0) continue;
if (map[nz][ny][nx] == 1 || map[nz][ny][nx] == -1) continue;
map[nz][ny][nx] = 1;
q.push({ nz,ny,nx,tmp.cnt + 1 });
}
}
printf("%d\n", result);
}
이 코드는 3차원 배열로 구성된 상자 속에 익은 토마토가 주어졌을 때, 모든 토마토가 익는 데 걸리는 최소 일수를 구하는 프로그램이다.
먼저 익은 토마토의 위치를 큐에 넣고, 상하좌우 앞뒤로 토마토가 익지 않은 곳을 찾아서 익은 상태로 바꾸고 큐에 넣는 과정을 반복한다. 이때, 큐에서 토마토를 꺼내면서 일수를 계산하고, 모든 토마토가 익었는지 확인하는 함수를 사용하여 모든 토마토가 익었을 때의 일수를 구한다.
