[알고리즘] 백준 7569 토마토

www.acmicpc.net/problem/7569

7569번: 토마토

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_7569 {
    static int n;
    static int m;
    static int h;
    static int[][][] map;
    static boolean[][][] visited;
    static int[] dx = {0, 0, -1, 1, 0, 0};
    static int[] dy = {-1, 1, 0, 0, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        map = new int[h + 1][n + 1][m + 1];
        visited = new boolean[h + 1][n + 1][m + 1];

        List list = new ArrayList<Location>();

        for (int k = 1; k < h + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                s = br.readLine();
                st = new StringTokenizer(s, " ");

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

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

        bfs(list);
    }

    static void bfs(List<Location> current) {
        Queue<Location> qu = new LinkedList<Location>();

        for (int i = 0; i < current.size(); i++) {
            qu.add(current.get(i));
        }

        while (!qu.isEmpty()) {
            Location temp = qu.poll();

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

                if (nx > 0 && nx < n + 1 && ny > 0 && ny < m + 1 && nz > 0 && nz < h + 1) {
                    if (map[nz][nx][ny] == 0) {
                        map[nz][nx][ny] = temp.day + 1;
                        qu.add(new Location(nx, ny, nz, temp.day + 1));
                    }
                }
            }
        }
        check();
    }

    static void check() {
        int result = 0;
        for (int i = 1; i < h + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                for (int k = 1; k < m + 1; k++) {
                    result = Math.max(result, map[i][j][k]);

                    if (map[i][j][k] == 0) {
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }

        if (result == 1)
            System.out.println(0);
        else
            System.out.println(result);
    }

    static class Location {
        int x;
        int y;
        int z;
        int day;

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

3차원 배열에 대하여 BFS를 수행하도록 하는 문제이다.

 

기존 상하좌우를 다루는 2차원 BFS문제에서 추가적으로 3차원 배열을 따져야한다.

 

2차원 BFS 문제에서는 아래와 같은 dx, dy를 사용하였다.

 

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

 

하지만 3차원 BFS를 풀기 위해서는 추가적으로 dz가 필요하다.

 

그를 위해서 dx와 dy의 size를 늘려주었다.

 

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

 

위 개념을 적용하는 것을 이해 했으면 기존 BFS와 마찬가지로 문제를 이해할 수 있을것이다.

 

if (nx > 0 && nx < n + 1 && ny > 0 && ny < m + 1 && nz > 0 && nz < h + 1)를 통해 인덱스의 유효성을 검증하고 (인덱스값이 1보다 작거나 bound를 넘어거나 하는 것을 예외처리)

 

아직 방문하지 않은 정점이기에 BFS를 수행해야 하는 경우라면

 

map[nz][nx][ny] = temp.day + 1 을 통해 현재 방문 인덱스까지 걸린 cost를 측정할 수 있다.

 

이 문제에서 주의해야 할 점은 토마토가 전부 익지 못할 경우 -1을 출력하는 것, 토마토가 처음부터 전부 익어있는 경우에는 0을 출력해야 하는 것이다.

 

문제를 한번더 자세하게 읽어보는 습관을 들여야 할 것 같다 ㅠ