[BOJ] 백준 7569 토마토

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

7569번: 토마토

 

---

 

풀이 방법

• 익은 토마토에 인접한 토마토들은 보관 후 하루가 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향으로 익게 된다.
• 앞, 뒤라는 조건이 있기 때문에 3차원 배열을 이용한다. 

3차원 배열에 대해서 간단히 설명하자면,

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

xyz는 일반적으로 x는 y와 z의 배열을 가진 면, y는 배열에서 열(Row), z는 배열에서 행(Column)을 지칭한다.

   

• 익은 토마토 즉, 값이 1인 좌표를 모두 큐에 넣고 너비 우선 탐색(bfs)을 돌린다. 값이 0인 익지 않은 토마토가 있는 곳을 찾아서 큐에 넣고, 이전 위치에 +1을 하여 토마토가 익는 일수를 구한다.
• bfs가 끝난 뒤, 익지 않은 토마토 즉, 값이 0인 곳이 있다면, 토마토가 모두 익을 수 없는 경우이므로 -1을 출력하고 그 외의 경우 배열에서 가장 큰 값을 구하면 그 값이 최소 일수가 된다.

 

다음은 Java로 작성한 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B7569 {
    private static final int[] dx = {0, 0, 0, 0, 1, -1};
    private static final int[] dy = {-1, 0, 1, 0, 0, 0};
    private static final int[] dz = {0, 1, 0, -1, 0, 0};
    private static int m, n, f;
    private static int[][][] map;
    private static final Queue<Point> queue = new LinkedList<>();

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

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        f = Integer.parseInt(st.nextToken());

        map = new int[f][n][m];

        for(int i = 0; i < f; i++){
            for(int j = 0; j < n; j++){
                st = new StringTokenizer(br.readLine());

                for(int k = 0; k < m; k++){
                    map[i][j][k] = Integer.parseInt(st.nextToken());

                    if(map[i][j][k] == 1) {
                        queue.add(new Point(i, j, k));
                    }
                }
            }
        }

        bfs();
    }

    private static void bfs() {
        while (!queue.isEmpty()) {
            Point point = queue.poll();

            int curX = point.x;
            int curY = point.y;
            int curZ = point.z;

            for (int dir = 0; dir < 6; dir++) {
                int nx = curX + dx[dir];
                int ny = curY + dy[dir];
                int nz = curZ + dz[dir];

                if (nx >= 0 && ny >= 0 && nz >=0 && nx < f && ny < n && nz < m) {
                    if (map[nx][ny][nz] == 0) {
                        queue.add(new Point(nx, ny, nz));
                        map[nx][ny][nz] = map[curX][curY][curZ] + 1;
                    }
                }
            }
        }

        maxValue();
    }

    private static void maxValue() {
        int max = 0;

        for (int k = 0; k < f; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[k][i][j] == 0) {
                        System.out.println(-1);
                        return;
                    }

                    max = Math.max(max, map[k][i][j]);
                }
            }
        }

        System.out.println(max-1);
    }

    private static class Point {
        int x; // 면
        int y; // 세로
        int z; // 가로

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