# BOJ07569 토마토

https://www.acmicpc.net/problem/7569 (opens new window)

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익는다.

하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.

# 토마토?

BOJ07576 토마토 (opens new window)

매우 유사한 문제이다. 단순히 탐색할 수 있는 범위가 4 -> 6로 늘어났다.

# Location.java

좌표를 관리하기 위한 Location 클래스이다.

private static class Location {
    int x, y, z;

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

# BFS 활용

주변 토마토를 익게 하기 위한 bfs 메소드이다. 만약 익은 토마토가 여러개 인 경우 하루가 지나면 동시 다발적으로 주변 토마토를 익게 만들 것이다. 그렇기 때문에 bfs가 시작하는 시점에 익은 토마토를 모두 queue에 저장한다.

private static void bfs() {
    Queue<Location> queue = new LinkedList<>();

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

    while (!queue.isEmpty()) {
        Location location = queue.poll();
        for (int i = 0; i < 6; i++) {
            int x = location.x + dx[i];
            int y = location.y + dy[i];
            int z = location.z + dz[i];

            if (isLocation(x, y, z)) {
                queue.add(new Location(x, y, z));
                graph[z][x][y] = graph[location.z][location.x][location.y] + 1;
            }
        }
    }
}

# 제출 코드

위에서 작성한 bfs를 활용하면 토마토가 전부 탐색되며 익힌 날짜를 늘려간다. 이때 전체 탐색하며 가장 큰 값을 뽑아낸다.

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

public class BOJ7569 {

    private static int m, n, h;
    private static int[][][] graph;

    // 상 하 좌 우 위 아래
    private static int[] dx = {-1, 1, 0, 0, 0, 0};
    private static int[] dy = {0, 0, -1, 1, 0, 0};
    private static int[] dz = {0, 0, 0, 0, -1, 1};

    private static class Location {
        int x, y, z;

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

    private static void bfs() {
        Queue<Location> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            for (int i = 0; i < 6; i++) {
                int x = location.x + dx[i];
                int y = location.y + dy[i];
                int z = location.z + dz[i];

                if (isLocation(x, y, z)) {
                    queue.add(new Location(x, y, z));
                    graph[z][x][y] = graph[location.z][location.x][location.y] + 1;
                }
            }
        }
    }

    private static boolean isLocation(int x, int y, int z) {
        if (x < 0 || x >= n || y < 0 || y >= m || z < 0 || z >= h || graph[z][x][y] != 0) {
            return false;
        }
        return true;
    }

    private static int getMax() {
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (graph[i][j][k] == 0) {
                        return -1;
                    }

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

        return max - 1;
    }

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

        m = scanner.nextInt(); // 가로
        n = scanner.nextInt(); // 세로
        h = scanner.nextInt(); // 높이

        graph = 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++) {
                    graph[i][j][k] = scanner.nextInt();
                }
            }
        }

        bfs();

        System.out.println(getMax());
    }
}
#BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #BFS
last updated: 10/11/2021, 4:01:29 PM