[백준] 7569 토마토 (JAVA)

✉️문제

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

7569번: 토마토

 

📝 접근

7576번과 똑같은 BFS 문제이다. 여기서 배열이 2차원 -> 3차원으로 변경된 문제라고 생각하면 된다.

https://brightmango.tistory.com/323

[백준] 7576 토마토 (JAVA)

 

 

🗝 문제풀이

1. 입력을 받을 때 박스의 아래부터 저장해야 하기 때문에 n - 1부터 시작하며, 만약 익은 토마토(1)이면 Queue에 바로 집어넣는다.

// 입력 받기 - 박스의 아래부터 저장해야 하므로 n-1부터 시작
for(int k = h-1; k >= 0; k--) {
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int t = sc.nextInt();
            box[k][i][j] = t;
            if (t == 1) q.add(new Point(k,i,j));
        }
    }
}

 

2. 앞, 뒤, 옆, 위, 아래에 대한 좌표를 dx,dy,dz를 이용해 표현해 준다. 

static int dx[] = {-1, 0, 0, 1, 0, 0};
static int dy[] = {0, -1, 1, 0, 0, 0};
static int dz[] = {0, 0, 0, 0, 1, -1};

 

3. Queue에 담긴 Point 객체를 하나씩 꺼낸다음, 현재 토마토(tmp)에 토마토가 익은 날짜(tmp+1)를 ch배열에 입력한다.

public static void BFS() {
    while(!q.isEmpty()) {
        Point tmp = q.poll();
        for(int i = 0; i < dx.length; i++) {
            int nx = tmp.x - dx[i];
            int ny = tmp.y - dy[i];
            int nh = tmp.h - dz[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && nh >= 0 && nh < h && box[nh][nx][ny] == 0) {
                box[nh][nx][ny] = 1;
                q.add(new Point(nh, nx, ny));
                ch[nh][nx][ny] = ch[tmp.h][tmp.x][tmp.y] + 1;
            }
        }
    }
}

 

전체코드

package baekjoon;

import java.util.*;

public class B7569 {

    static int dx[] = {-1, 0, 0, 1, 0, 0};
    static int dy[] = {0, -1, 1, 0, 0, 0};
    static int dz[] = {0, 0, 0, 0, 1, -1};

    static int[][][] ch, box;
    static int m,n,h;
    static Queue<Point> q = new LinkedList<>();

    static class Point {
        int h, x, y;

        public Point(int h, int x, int y) {
            this.h = h;
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt(); // 가로칸 수
        n = sc.nextInt(); // 세로칸 수
        h = sc.nextInt(); // 상자의 수

        box = new int[h][n][m];
        ch = new int[h][n][m];

        // 입력 받기 - 박스의 아래부터 저장해야 하므로 n-1부터 시작
        for(int k = h-1; k >= 0; k--) {
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >= 0; j--) {
                    int t = sc.nextInt();
                    box[k][i][j] = t;
                    if (t == 1) q.add(new Point(k,i,j));
                }
            }
        }

        BFS();

        if(checkTomato()) System.out.print(findLastDay());
        else System.out.print(-1);
    }

    private static int findLastDay() {
        int answer = Integer.MIN_VALUE;
        for(int i = h-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                for(int k = m-1; k >= 0; k--) {
                    answer = Math.max(answer, ch[i][j][k]);
                }
            }
        }
        return answer;
    }

    private static boolean checkTomato() {
        for(int k = h -1; k >= 0; k--) {
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >= 0; j--) {
                    if(box[k][i][j] == 0) return false;
                }
            }
        }
        return true;
    }

    // 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토 x
    // 토마토는 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향으로 익게 만든다.
    public static void BFS() {
        while(!q.isEmpty()) {
            Point tmp = q.poll();
            for(int i = 0; i < dx.length; i++) {
                int nx = tmp.x - dx[i];
                int ny = tmp.y - dy[i];
                int nh = tmp.h - dz[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && nh >= 0 && nh < h && box[nh][nx][ny] == 0) {
                    box[nh][nx][ny] = 1;
                    q.add(new Point(nh, nx, ny));
                    ch[nh][nx][ny] = ch[tmp.h][tmp.x][tmp.y] + 1;
                }
            }
        }
    }
}