[백준] 7569번 토마토

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q7569.java

이전 토마토 문제의 확장 문제이다. 상자가 여러겹 쌓여있으며 익은 토마토가 위 아래 상자의
토마토에까지 영향을 끼친다.

처음 생각

우선 이전 토마토 문제인 [백준] 7576번 토마토 와 풀이를 똑같이 했다.

▶ 다른점이라면 위 아래 상자를 생각해줘야 한다는 것이였다.

다음 생각

한 상자를 사용할 때 2차 배열로 표현할 수 있었다. 그럼 문제가 간단해진다. 층을 표현할 위치를 추가해서 3차 배열로 표현을 해주었다.

▶ [층][그 층의 토마토 x 위치][그 층의 토마토 y 위치]로 배열을 사용하였다.

▶ 기존의 문제에서 배열로 주변 토마토들의 BFS 탐색을 진행하였듯이 다른 상자의 탐색도 미리 배열로 좌표를 만들어 놓고 탐색을 진행하였다.

다다음 생각

기존 입력을 Scanner를 사용해서 문제를 풀었었고, 주어지는 배열의 크기가 최대 100 x 100이므로 입력을 BufferedReader로 바꾸어 메모리 감소와 시간 단축을 시켰다.

▶ 입력이 확실히 많은경우는 BufferedReader를 사용하는 것이 효율적이다.

방안

1) Java 풀이

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

package baekjoon.q1000;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer;   public class Q7569 {     static int m,n,h;     static int[][][] arr;     static Queue<Pair> queue = new LinkedList<>();     public static void main(String args[]) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         m = Integer.parseInt(st.nextToken()); // 상자 가로칸         n = Integer.parseInt(st.nextToken()); // 세로         h = Integer.parseInt(st.nextToken()); // height         arr = new int[h][n][m];           for(int i=0;i<h;i++){             for(int j=0;j<n;j++){                 st = new StringTokenizer(br.readLine());                 for(int k=0;k<m;k++) {                     arr[i][j][k] = Integer.parseInt(st.nextToken());                     if(arr[i][j][k]==1) queue.add(new Pair(i,j,k));                 }             }         }           solve();     }       static int[] dirH = {1,-1};     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static void solve(){         int result = -1;         while(!queue.isEmpty()){             int size = queue.size();             result++;             for(int i=0;i<size;i++){                 Pair t = queue.poll();                 // 주변 토마토                 for(int j=0;j<4;j++){                     int tx = t.n + dir[j][0];                     int ty = t.m + dir[j][1];                     if(tx<0 || ty<0 || tx>=n || ty>=m) continue;                     if(arr[t.h][tx][ty]!=0) continue;                     arr[t.h][tx][ty] = 1;                     queue.add(new Pair(t.h,tx,ty));                 }                 // 위 아래 토마토                 for(int j=0;j<2;j++){                     int th = t.h+dirH[j];                     if(th<0 || th>=h) continue;                     if(arr[th][t.n][t.m]!=0) continue;                     arr[th][t.n][t.m] = 1;                     queue.add(new Pair(th,t.n,t.m));                 }             }         }         // 토마토가 남아있는지 탐색         for(int i=0;i<h;i++){             for(int j=0;j<n;j++){                 for(int k=0;k<m;k++) {                     // 안 익은 토마토가 있다면 -1 출력                     if(arr[i][j][k]==0){                         System.out.println(-1);                         return;                     }                 }             }         }         System.out.println(result);     }       static class Pair{         int h,n,m;         Pair(int h,int n,int m){             this.h = h;             this.n = n;             this.m = m;         }     } }