알고리즘/완전탐색(BFS,DFS)
BOJ - 7569 ) 토마토
개발자가될수있을까?
2020. 1. 22. 21:43
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
3차원 공간에서 토마토를 큐에 넣으면서
인접한 토마토에 영향을 미치는지 여부를 판단하는 문제이다.
예외로 입력을 받았을때에, 0이 있는지 확인하는 메소드를 만들어 체크해주었다.
|
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
102
103
104
105
106
|
import java.util.LinkedList;
import java.util.Queue;
class coordi{
int x;
int y;
int z;
int time;
coordi(int x ,int y, int z , int time){
this.x =x;
this.y =y;
this.z =z;
this.time = time;
}
}
public class Main {
static int dx[] = {0,0,-1,+1,0,0};
static int dy[] = {+1,-1,0,0,0,0};
static int dz[] = {0,0,0,0,+1,-1};
static int count =0;
static int x,y,z;
static int map[][][];
public static boolean judge() {
for(int h = 0 ; h < z ; h++) {
for(int n = 0 ; n < y; n++) {
for(int m = 0 ; m < x ; m++) {
if(map[h][n][m]== 0) {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
Queue<coordi> Q = new LinkedList<coordi>();
x = sc.nextInt();
y = sc.nextInt();
z = sc.nextInt();
map = new int[z][y][x];
boolean visit[][][] = new boolean[z][y][x];
for(int h = 0 ; h < z ; h++) {
for(int n = 0 ; n < y; n++) {
for(int m = 0 ; m < x ; m++) {
map[h][n][m] = sc.nextInt();
if(map[h][n][m]== -1) visit[h][n][m] =true;
if(map[h][n][m]== 1) Q.add(new coordi(m,n,h,0));
}
}
}
if(judge()) {
System.out.println(0);
}
else {
while(!Q.isEmpty()) {
coordi now = Q.poll();
for(int index = 0 ; index <6 ; index++) {
int nx = now.x + dx[index];
int ny = now.y + dy[index];
int nz = now.z + dz[index];
if(nx >= 0 && ny >= 0 && nz >= 0 && nx < x && ny < y && nz < z && !visit[nz][ny][nx]) {
if(map[nz][ny][nx] == 0) {
map[nz][ny][nx] = 1;
visit[nz][ny][nx] = true;
}
}
}
}
// for(int h = 0 ; h < z ; h++) {
// for(int n = 0 ; n < y; n++) {
// for(int m = 0 ; m < x ; m++) {
// if( map[h][n][m] == 1 && !visit[h][n][m]) {
//
//
// }
// }
// }
// }
//
if(judge()) {
System.out.println(count);
}
else {
System.out.println(-1);
}
}
}
}
|
