99클럽 코테 스터디 12일차 TIL (7569번: 토마토)

문제

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

 

---

학습 키워드

• BFS

 

시도

• (시간 초과) 완전 탐색
  1. day를 1부터 H*N*M 까지 탐색하면서 모든 배열을 순회하면서 토마토를 익히고, 익은 개수를 센다.
  2. 첫 째날부터 익은 토마토가 없다면 0을 반환한다.
  3. 익은 토마토가 없다면 날짜를 출력한다. 이때, 배열에 0이 포함되어 있다면 -1을 출력하고, 아니라면 날짜를 출력한다.
• (성공) 익은 토마토를 기준으로 BFS
  1. 값을 입력 받을 때, Queue에 익은 토마토의 위치를 추가한다. 이때, 현재 토마토가 익은 날짜가 언제인지 알 수 있는 값도 같이 추가한다.
  2. BFS 방식으로 Queue의 맨 앞 값(poll)을 빼내주면서하면서 익은 토마토 주변('앞', '뒤', '상', '하', '좌', '우')에 있는 익지 않은 토마토를 찾고, 그 토마토를 Queue에 저장한다. 이때, 그 토마토는 '1'로 바꿔주어 익은 토마토로 변경해준다.
  3. Queue를 순회를 하면서 익은 토마토의 최대 일 수를 저장한다.
  4. 더 이상 익힐 수 있는 토마토가 없다면 최대 일 수를 반환한다.

풀이 및 코드

• class Coordinate
  • h: 높이
  • r: 세로의 길이
  • c: 가로의 길이
  • grownDay: 익은 날짜
• arr3d: 각 위치에 있는 토마토의 현재 상태를 저장하는 변수
• Queue<Coordinate> grownTomatoes: 익은 토마토를 저장하는 변수
• totalGrownDay: 토마토가 익을 날짜의 최대값을 저장하는 변수

import java.util.*;
import java.io.*;

class Coordinate {
    int h;
    int r;
    int c;
    int grownDay;

    Coordinate(int h, int r, int c) {
       this.h = h;
       this.r = r;
       this.c = c;
       this.grownDay = 0;
    }

    Coordinate(int h, int r, int c, int grownDay) {
       this.h = h;
       this.r = r;
       this.c = c;
       this.grownDay = grownDay;
    }
}

public class Main {

    private static StringTokenizer st;

    private static final int DIRECTION_COUNT = 6;

    private static final int[] dh = new int[] {0, 0, 0, 0, 1, -1};
    private static final int[] dr = new int[] {-1, 0, 1, 0, 0, 0};
    private static final int[] dc = new int[] {0, 1, 0, -1, 0, 0};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       st = new StringTokenizer(br.readLine());
       int M = Integer.parseInt(st.nextToken()); // column
       int N = Integer.parseInt(st.nextToken()); // row
       int H = Integer.parseInt(st.nextToken()); // height

       int[][][] arr3d = new int[H][N][M];
       Queue<Coordinate> grownTomatoes = new LinkedList<>();
       for (int h = 0; h < H; h++) {
          for (int r = 0; r < N; r++) {
             st = new StringTokenizer(br.readLine());
             for (int c = 0; c < M; c++) {
                int tomatoStatus = Integer.parseInt(st.nextToken());
                arr3d[h][r][c] = tomatoStatus;
                if (tomatoStatus == 1) {
                   grownTomatoes.add(new Coordinate(h, r, c));
                }
             }
          }
       }

       int totalAllGrownDay = tomatoesGrownAndGetAllGrownDay(arr3d, grownTomatoes, H, N, M);
       if (hasNonGrownTomato(arr3d, H, N, M)) {
          System.out.println("-1");
       } else {
          System.out.println(totalAllGrownDay);
       }

    }

    private static boolean hasNonGrownTomato(int[][][] arr3d, int H, int N, int M) {
       for (int h = 0; h < H; h++) {
          for (int r = 0; r < N; r++) {
             for (int c = 0; c < M; c++) {
                if (arr3d[h][r][c] == 0) {
                   return true;
                }
             }
          }
       }
       return false;
    }

    private static int tomatoesGrownAndGetAllGrownDay(int[][][] arr3d, Queue<Coordinate> grownTomatoes, int H, int N, int M) {
       int totalGrownDay = 0;

       while (!grownTomatoes.isEmpty()) {
          Coordinate current = grownTomatoes.poll();

          for (int d = 0; d < DIRECTION_COUNT; d++) { // 익은 토마토가 주변에 있는지 확인한다.
             int nh = current.h + dh[d];
             int nr = current.r + dr[d];
             int nc = current.c + dc[d];
             totalGrownDay = current.grownDay;
             if (!check(H, N, M, nh, nr, nc)) { // 유효한 좌표인가?
                continue;
             }
             if (arr3d[nh][nr][nc] == 0) { // 익은 토마토인가?
                grownTomatoes.add(new Coordinate(nh, nr, nc, current.grownDay + 1));
                arr3d[nh][nr][nc] = 1;
             }
          }
       }
       return totalGrownDay;
    }

    private static boolean check(int H, int N, int M, int h, int r, int c) {
       if (h < 0 || r < 0 || c < 0) {
          return false;
       }
       if (h >= H || r >= N || c >= M) {
          return false;
       }
       return true;
    }

    private static void print(int[][][] arr3d) {
       for (int h = 0; h < arr3d.length; h++) {
          for (int r = 0; r < arr3d[0].length; r++) {
             for (int c = 0; c < arr3d[0][0].length; c++) {
                System.out.print(arr3d[h][r][c] + " ");
             }
             System.out.println();
          }
          System.out.println();
       }
    }
}