[Java]백준 7569번 :: 토마토

백준 온라인 저지 7569번 - 토마토

Java 알고리즘 문제풀이

풀이

BFS(너비 우선 탐색) 문제입니다.

BFS를 이용해 해결하는 문제는 3가지 조건을 가지고 있다.

1. 최소 비용 문제

2. 간선의 가중치가 1이다.

3. 정점과 간선의 개수가 적다. (시간제한, 메모리 제한 내에 만족한다.)

DFS, BFS 관련 자료 : https://developer-mac.tistory.com/64

 

토마토 문제에서는 BFS를 이용하면 된다.

익은 토마토를 큐에 담아 좌, 우, 위, 아래 총 4가지 경로를 탐색해주면된다.

이때 익은 토마토 기준으로 다른 칸으로 갈때 (안익은 토마토 0이 있을 때만, 비어 있는 공간 -1일 때는 제외한다.) 

 

그리고 3차원 배열을 사용했기 때문에 이전 토마토 문제보다 신경써줘야 할 것들이 있다.

int[][][] arr = new int[x][y][z]

위 배열이 있다면 z를 일반적으로 가로에 나열되는 수라고 생각하면 되고, y는 세로, x는 y와 x의 배열을 가지고 있는 면이라고 생각하면 된다.

z = 가로

y = 세로

x = 면

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

class Three {
    int x;
    int y;
    int z;

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

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

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

        Queue<Three> queue = new LinkedList<Three>();

        int[][][] arr = new int[h][n][m];
        int[][][] dist = new int[h][n][m];

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

        while (!queue.isEmpty()) {
            Three t = queue.remove();
            int x = t.x;
            int y = t.y;
            int z = t.z;
            for (int i = 0; i < dy.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nz = z + dz[i];

                if (0 <= nx && nx < h && 0 <= ny && ny < n && 0 <= nz && nz < m) {
                    if (arr[nx][ny][nz] == 0 && dist[nx][ny][nz] == 0) {
                        queue.add(new Three(nx, ny, nz));
                        dist[nx][ny][nz] = dist[x][y][z] + 1;
                    }
                }
            }
        }

        int ans = 0;

        for (int k = 0; k < h; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (ans < dist[k][i][j])
                        ans = dist[k][i][j];
                }
            }
        }

        for (int k = 0; k < h; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[k][i][j] == 0 && dist[k][i][j] == 0) {
                        ans = -1;
                    }
                }
            }
        }

        System.out.println(ans);

        sc.close();
    }
}