문제 출처 : https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마
www.acmicpc.net
이 문제는 BFS 기법을 이용하여 해결하는 문제이다.
저번 상범 빌딩과 같이 3차원으로 dx, dy, dz 배열을 이용하여 해결 할 수 있었다.
아래는 해당 문제를 풀이한 소스 코드이다.
|
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include<stdio.h>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
int M;
int N;
int H;
int arr[101][101][101];
int dx[6] = {0,0, 1,-1,0,0 };
int dy[6] = {0,0, 0,0,1,-1 };
int dz[6] = { 1, -1, 0, 0, 0, 0 };
int value = 0;
struct list
{
int x;
int y;
int z;
int cnt = 0;
};
queue <list> que;
void BFS()
{
{
int size = que.size();
for (int j = 0; j < size; j++)
{
int x = que.front().x;
int y = que.front().y;
int z = que.front().z;
que.pop();
for (int i = 0; i < 6; i++)
{
int temp_z = z + dz[i];
int temp_x = x + dx[i];
int temp_y = y + dy[i];
if (temp_x >= 0 && temp_x < N && temp_y >= 0 && temp_y < M && temp_z>=0 && temp_z<H)
{
if (arr[temp_z][temp_x][temp_y] == 0)
{
list temp;
temp.x = temp_x;
temp.y = temp_y;
temp.z = temp_z;
arr[temp_z][temp_x][temp_y] = 1;
}
}
}
}
value++;
}
}
bool find()
{
for (int k = 0; k < H; k++)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (arr[k][i][j] == 0)
return false;
}
}
}
return 1;
}
int main()
{
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", &arr[k][i][j]);
if (arr[k][i][j] == 1)
{
list temp;
temp.x = i;
temp.y = j;
temp.z = k;
}
}
}
}
if (que.empty())
{
printf("0");
return 0;
}
BFS();
if (find())
printf("%d", value - 1);
else
printf("-1");
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 16397번 문제 ( 탈출 ) (0) | 2020.02.18 |
|---|---|
| 백준 9019번 문제 ( DSLR ) (0) | 2020.02.18 |
| 백준 6593번 문제 ( 상범 빌딩 ) (0) | 2020.02.18 |
| 백준 5427번 문제 ( 불 ) (0) | 2020.02.18 |
| 백준 2206번 문제 ( 벽 부수고 이동하기 ) (0) | 2020.02.14 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~