[Java] 백준 7569 : 토마토

문제 링크

1.

이전에 풀었던 토마토 문제의 응용문제이다.

2차원 배열이었다면 이번에는 3차원 배열..

 

3차원 배열을 너무 오랜만에 써서 맨 앞의 인덱스가 행이었나 면이었나 기억이 안 났다.

또 모두 익을 때까지 며칠이 걸리는지 카운트하는 부분에서 살짝 헤맸다.

 

 

2.

BFS로 풀었다.

dx, dy, dz 배열로 이동할 6가지 방향(상, 하, 좌, 우, 앞, 뒤)을 잡아준다.

 

1. 배열 전체를 순회하며 익은 토마토가 있는 부분을 queue에 넣는다.

 

2. queue가 empty일 때까지 다음을 반복한다.

  2-1. queue에서 원소를 하나씩 빼서 6가지 방향에 대하여

  2-2. 해당 방향에 익지 않은 토마토가 있다면 익게 하고 queue에 넣는다.

        단, 익게 할 때 단순히 1로 바꾸는 것이 아니라 이동하기 전 원소 + 1을 해준다. (day 증가)

 

3. 배열 전체를 순회하며

  3-1. 0인 원소가 있다면 모두 익지 못하는 상황이므로 -1을 출력한다.

  3-2. 가장 큰 원소 - 1을 출력한다. (처음 익은 토마토가 있던 자리의 1을 빼줘야 하기 때문이다.)

 

 

3.

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

public class Main {
    static int m, n, h, answer = 1;
    static int[][][] data;

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

        m = sc.nextInt();
        n = sc.nextInt();
        h = sc.nextInt();

        data = new int[h][n][m];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    data[i][j][k] = sc.nextInt();
                }
            }
        }

        bfs();

        boolean flag = true;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (data[i][j][k] == 0) {
                        flag = false;
                        break;
                    } else {
                        answer = Math.max(answer, data[i][j][k]);
                    }
                }
            }
        }
        System.out.println(flag ? --answer : -1);
        sc.close();
    }

    static void bfs() {
        Queue<Pos> q = new LinkedList<>();

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

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (data[i][j][k] == 1) {
                        q.offer(new Pos(i, j, k));
                    }
                }
            }
        }

        while (!q.isEmpty()) {
            Pos temp = q.poll();

            for (int t = 0; t < 6; t++) {
                int nx = temp.x + dx[t];
                int ny = temp.y + dy[t];
                int nz = temp.z + dz[t];

                if (0 <= nx && nx < n && 0 <= ny && ny < m && 0 <= nz && nz < h) {
                    if (data[nz][nx][ny] == 0) {
                        data[nz][nx][ny] = data[temp.z][temp.x][temp.y] + 1;
                        q.offer(new Pos(nz, nx, ny));
                    }
                }
            }
        }

    }
}

class Pos {
    int x, y, z;

    public Pos(int z, int x, int y) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

 

 

4.

3차원 배열

arr[3][4][5]라면 3면 4행 5열이라는 의미이다.

그림으로 표현하면 다음과 같다.

 

 

 

[참고] https://developer-mac.tistory.com/68

[그림] https://m.blog.naver.com/skout123/50129381927