<Algorithm> 36. 7569번 토마토

1. 7569번 토마토

• 7576번 토마토의 응용 문제, BFS를 사용하는 기본 문제로 3차원 배열을 사용하여 문제 풀이

• 앞 뒤 왼쪽 오른쪽 위 아래 총 6가지의 변화량을 잘 잡아주기만 하면 된다.

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

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 Main {     static int[][][] dist;      static int max = 0;     public static void main(String[] args) throws NumberFormatException, 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 H = Integer.parseInt(st.nextToken());                  int[][][] arr = new int[N][M][H];         dist = new int[N][M][H];                  for(int k = 0; k < H; k++) {             for(int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine());                 for(int j = 0; j < M; j++) {                     arr[i][j][k] = Integer.parseInt(st.nextToken());                 }             }         }           Queue<Location> queue = new LinkedList<>();             for(int k = 0; k < H; k++) {             for(int i = 0; i < N; i++) {                 for(int j = 0; j < M; j++) {                     if(arr[i][j][k] == 1) {                         queue.add(new Location(i, j, k));                         dist[i][j][k] = 0;                     }                 }             }         }                  bfs(arr, queue, N, M, H);                  for(int k = 0; k < H; k++) {             for(int i = 0; i < N; i++) {                 for(int j = 0; j < M; j++) {                     if(arr[i][j][k] == 0) {                         System.out.println(-1);                         return;                     }                 }             }         }             System.out.println(max);     }          public static void bfs(int[][][] arr, Queue<Location> queue, int N, int M, int H) {         int[] dx = {0, 0, 1, -1, 0, 0};         int[] dy = {1,-1, 0, 0, 0, 0};                 int[] dz = {0, 0, 0,  0, -1, 1}; // 변화량 총 6가지                  while(!queue.isEmpty()) {             Location loc = queue.remove();             int x = loc.x;             int y = loc.y;             int z = loc.z;                          for(int i = 0; i < dx.length; i ++) {                 int nx = x+ dx[i];                 int ny = y+ dy[i];                 int nz = z+ dz[i];                                  if(nx >= 0 && ny >= 0 && nz >= 0 && nx < N && ny < M && nz < H && arr[nx][ny][nz] == 0 ) {                     dist[nx][ny][nz] = dist[x][y][z] + 1;                                          queue.add(new Location(nx, ny, nz));                     arr[nx][ny][nz] = 1;                                          if(max < dist[nx][ny][nz]) {                         max = dist[nx][ny][nz];                     }                 }             }         }     }          } class Location{     int x;     int y;     int z;     public Location(int x, int y,int z) {         this.x = x;         this.y = y;         this.z = z;     } } Colored by Color Scripter

cs