BOJ_7569 : 토마토

👉 문제링크

7569번: 토마토

---

---

🔸 문제 분석 🔸

• H x N x M 크기의 창고에 익거나 덜 익은 토마토가 들어있다. 
  • 익은 토마토는 상하좌우전후의 덜 익은 토마토를 다음 날 익게 한다.
  • 빈 칸도 있다.
  • 토마토가 모두 익을 때 까지 최소 며칠이 걸리는지 출력한다.
  • 모두 익지 못하면 -1을 출력한다.
• BFS를 통해 익은 토마토 옆 덜 익은 토마토들이 모두 익을 때 까지 걸리는 날을 계산한다.
  • 큐에서 방금 익은 토마토의 좌표를 꺼낸다.
  • 꺼낸 토마토 주변의 덜 익은 토마토의 값을 현재 값+1 로 바꾸고, 좌표를 큐에 넣는다.
  • 큐가 빌 때 까지 반복한다.
• 토마토 창고에서 가장 큰 값을 출력한다.
  • 0이 있으면 -1을 반환한다. (모두 익을 수 없음)

🔸 코드 🔸

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // input
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int h = sc.nextInt();
        int[][][] arr = new int[h][n][m];

        Queue<Tomato> que = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    arr[i][j][k] = sc.nextInt();
                    if (arr[i][j][k] == 1)
                        que.add(new Tomato(j, k, i));
                }
            }
        }

        // BFS
        //          전 우 후 좌 상 하
        int[] dx = {-1, 0, 1, 0, 0, 0};
        int[] dy = {0, 1, 0, -1, 0, 0};
        int[] dz = {0, 0, 0, 0, 1, -1};

        while(!que.isEmpty()) {
            Tomato tomato = que.poll();

//            System.out.println(tomato.h + " " + tomato.n + " " + tomato.m);
//            print(arr);


            for (int i = 0; i < dx.length; i++) {
                int x = tomato.n + dx[i];
                int y = tomato.m + dy[i];
                int z = tomato.h + dz[i];

                if (0 <= x && x < n &&
                    0 <= y && y < m &&
                    0 <= z && z < h &&
                    arr[z][x][y] == 0) {
                    arr[z][x][y] = arr[tomato.h][tomato.n][tomato.m] + 1;
                    que.add(new Tomato(x,y,z));
                }
            }
        }
//        print(arr);

        System.out.println(tomato(arr));

    }
    private static int tomato(int[][][] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                for (int k = 0; k < arr[i][j].length; k++) {
                    if (arr[i][j][k] == 0)
                        return -1;
                    if (arr[i][j][k] > max)
                        max = arr[i][j][k];
                };
            }
        }
        return max-1;
    }

    private static class Tomato {
        int n, m, h;

        public Tomato(int n, int m, int h) {
            this.n = n;
            this.m = m;
            this.h = h;
        }
    }
    private static void print(int[][][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                for (int k = 0; k < arr[i][j].length; k++) {
                    System.out.print(arr[i][j][k] + " ");
                }
                System.out.println();
            }
            System.out.println("\n----------------------------------------\n");
        }
        System.out.println("\n==========================================\n");
    }
}

🔸 코드 해석 🔸

• 창고의 높이 h, 세로 너비 n, 가로 너비 h를 입력받고 창고 배열 arr에 값을 저장한다.
  • 큐를 만들어서 arr에 값을 넣을 때 1인 좌표를 초기값으로 넣어준다.
  • 좌표를 저장하기 위해 Tomato 클래스를 만들어 h, n, m 값을 속성으로 저장한다.
• BFS를 수행한다.
  • 좌표 이동을 위해 전좌후우상하 방향의 h,n,m 인덱스 변화 배열 dx, dy, dz를 초기화 한다.
  • 큐가 빌 때까지 계산을 반복한다.
    • 큐에서 Tomato 객체를 하나 poll() 한다.
    • 6방향의 h, m, n 이동을 확인해서 창고 범위 내이며 값이 0이면 현재 값+1을 저장하고 해당 좌표를 큐에 저장한다.
• arr에 0이 남아있으면 -1을 출력하고, 없다면 arr의 원소 중 최대값-1을 출력한다.

---

🔸 end 🔸

• 이전 토마토는 큐를 2개를 사용해 복사하며 풀이했는데, arr에 값을 누적하는 방식의 풀이를 보고 이번에 적용해보았다.
  • BFS에서 사용하기 아주 좋은 방법인 것 같다.
• print메서드는 보통 지우는데, 이번엔 있는 그대로 올렸다.
  • 생각보다 나쁘지 않은 것 같아서 코드에 남겨두려고 한다.
• 같은 알고리즘의 문제를 풀었더니 적을 것들이 많지 않았다.
  • 계속 간단히 쓸 수 있도록 연습할 생각이다.