제출 코드
- 사용 알고리즘 :
bfs
이 문제에서 차원만 하나 확장된 문제이다. bfs를 3차원 배열 상에서 시행하는 문제.
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
package gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class G7569_tomato {
static int[] di = {-1, 0, 1, 0, 0, 0};
static int[] dj = {0, 1, 0, -1, 0, 0};
static int[] dk = {0, 0, 0, 0, 1, -1};
static class Tomato{
int i, j, k;
Tomato(int i, int j, int k){
this.i = i;
this.j = j;
this.k = k;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][][] box = new int[K][N][M];
Queue<Tomato> queue = new LinkedList<Tomato>();
int remains = 0;
for(int k=0; k<K; k++) {
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
box[k][i][j] = Integer.parseInt(st.nextToken());
if(box[k][i][j]==0) remains++;
else if(box[k][i][j]==1) queue.add(new Tomato(i, j, k));
}
}
}
int time = 0;
loop : while(!queue.isEmpty()) {
if(remains==0) break;
time++;
int size = queue.size();
for(int i=0; i<size; i++) {
Tomato now = queue.poll();
for(int d=0; d<6; d++) {
int ni = di[d] + now.i;
int nj = dj[d] + now.j;
int nk = dk[d] + now.k;
if(ni<0 || ni>=N || nj<0 || nj>=M || nk<0 || nk>=K || box[nk][ni][nj]!=0) continue;
box[nk][ni][nj] = 1;
queue.add(new Tomato(ni, nj, nk));
if(--remains==0) break loop;
}
}
}
if(remains!=0) System.out.println(-1);
else System.out.println(time);
}
}