[BOJ] 7569. 토마토(BFS).java

#. Problem

https://www.acmicpc.net/problem/7569

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

7576. 토마토 문제의 상위(?) 문제이다.

7576번 문제는 하나의 상자였지만 이번에는 여러 상자가 쌓여있다.

하지만 당황하지 않아도 된다!

상,하,좌,우를 확인하고 추가로 위, 아래만 더 확인해주면 되니깐..

#. Code

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

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 BOJ7569 {       static int dx[] = { -1, 0, 1, 0 };     static int dy[] = { 0, 1, 0, -1 };     static int dh[] = {-1, 1};     static int N, M, H, cntZero, res, map[][][];     static Queue<pnt> q;       static public class pnt {         int h;         int x;         int y;           public pnt(int h, int x, int y) {             this.h = h;             this.x = x;             this.y = y;         }     }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           st = new StringTokenizer(br.readLine(), " ");         M = Integer.parseInt(st.nextToken()); // 가로         N = Integer.parseInt(st.nextToken()); // 세로         H = Integer.parseInt(st.nextToken());         map = new int[H][N][M];         q = new LinkedList<>();         cntZero = 0;         for (int h = 0; h < H; h++) {             for (int x = 0; x < N; x++) {                 st = new StringTokenizer(br.readLine(), " ");                 for (int y = 0; y < M; y++) {                     map[h][x][y] = Integer.parseInt(st.nextToken());                     // 익은 토마토의 위치를 Queue에 add                     if (map[h][x][y] == 1) q.offer(new pnt(h, x, y));                     // 익지 않은 토마토 count                     if (map[h][x][y] == 0) cntZero++;                 }             }         }         // 모든 토마토가 익어있는 상태라면         if(cntZero == 0) {             System.out.println("0");             return;         }                  res = -1;         bfs();                  // 아직 덜 익은 토마토가 있다면         if(cntZero != 0) System.out.println("-1");         else System.out.println(res);     }          public static void bfs() {         // 익은 토마토의 위치를 Queue에서 꺼내면서 주변 토마토를 익혀보자         while (!q.isEmpty()) {             // 현재 Queue Size를 미리 저장             int tmpN = q.size();             res++;             for (int day = 0; day < tmpN; day++) {                 pnt tmp = q.poll();                 // 인접한 안 익은 토마토 찾기(상,하,좌,우)                 for (int i = 0; i < 4; i++) {                     int xx = tmp.x + dx[i];                     int yy = tmp.y + dy[i];                     // 범위를 벗어날 경우 pass                     if(xx < 0 || yy < 0 || xx >= N || yy>=M) continue;                     // 인접한 토마토가 익지 않았다면 익혀주고 Queue에 넣기                     if(map[tmp.h][xx][yy] == 0) {                         map[tmp.h][xx][yy] = 1;                         cntZero--;                         q.offer(new pnt(tmp.h, xx, yy));                     }                 }                 // 인접한 안 익은 토마토 찾기(위,아래)                 for (int i = 0; i < 2; i++) {                     int hh = tmp.h + dh[i];                     // 범위를 벗어날 경우 pass                     if(hh < 0 || hh >= H) continue;                     // 인접한 토마토가 익지 않았다면 익혀주고 Queue에 넣기                     if(map[hh][tmp.x][tmp.y] == 0) {                         map[hh][tmp.x][tmp.y] = 1;                         cntZero--;                         q.offer(new pnt(hh, tmp.x, tmp.y));                     }                 }             }         }     } }   Colored by Color Scripter

cs