• 문제: https://www.acmicpc.net/problem/7569

설명

이번 문제는 BFS 알고리즘으로 토마토가 모두 익는데 걸리는 날짜를 계산한다. 알고리즘으로 풀이하는 것은 어렵지 않았으나 메모리 초과가 발생했다.

package Algorithm.P7569;

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

public class P7569 {
    static StringBuilder sb;
    static int M, N, H;			
    static boolean[][][] visited;
    static int[][][] tomatos;
    static int days = -1;
    static Queue<Point> queue = new LinkedList<>();

    static Point[] direction = {
    		new Point(0, 1, 0),
            new Point(1, 0, 0),
            new Point(-1, 0, 0),
            new Point(0, -1, 0),
            new Point(0, 0, 1),
            new Point(0, 0, -1)};
    static int z_temp, y_temp, x_temp;
    static int z_ttemp, y_ttemp, x_ttemp;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P7569/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());


        tomatos = new int[H][N][M];
        visited = new boolean[H][N][M];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < M; k++) {
                    tomatos[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tomatos[i][j][k] == 1) {
                        queue.add(new Point(k, j, i));
                        visited[i][j][k] = true;
                    } else if (tomatos[i][j][k] == -1) {
                        visited[i][j][k] = true;
                    } else visited[i][j][k] = false;
                }
            }
        }

        while (!queue.isEmpty()) {
            days++;
            int tryNumber = queue.size();

            while (tryNumber > 0) {
                Point temp = queue.poll();
                z_temp = temp.getZ();
                y_temp = temp.getY();
                x_temp = temp.getX();

                visited[z_temp][y_temp][x_temp] = true;
                tomatos[z_temp][y_temp][x_temp] = 1;

                for (int i = 0; i < 6; i++) {
                    z_ttemp = z_temp + direction[i].getZ();
                    y_ttemp = y_temp + direction[i].getY();
                    x_ttemp = x_temp + direction[i].getX();

                    if (x_ttemp < 0 || y_ttemp < 0 || z_ttemp < 0 ||
                            x_ttemp >= M || y_ttemp >= N || z_ttemp >= H) {
                        continue;
                    }

                    if (visited[z_ttemp][y_ttemp][x_ttemp] == false) {
                        queue.add(new Point(x_ttemp, y_ttemp, z_ttemp));
                    }
                }
                tryNumber--;
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tomatos[i][j][k] == 0) {
                        days = -1;
                        sb.append(days);
                        System.out.println(sb);
                        System.exit(0);
                    }
                }
            }
        }
        sb.append(days);
        System.out.println(sb);
    }

    private static boolean finishVisit() {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tomatos[i][j][k] == 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

첫번째 코드를 살펴보자.
토마토가 다 익는지 걸리는 시간을 day라는 변수에서 관리한다. days가 늘어나는 것을 하루에 접근가능한 토마토만큼 단위로 진행했다.

day 기준으로 queue에 몇개 들어있는지 확인하다보니, bfs에 n*n이 발생했다. -> 이 부분은 시간 복잡도이고, 불필요한 temp 변수와 class object를 사용하여 방향을 정의한 것이 메모리 초과 원인이된다. java에서 object는 항상 8의 배수만큼 byte 공간을 차지하기 때문이다.(참고)

while (!queue.isEmpty()) {
	days++;
    int tryNumber = queue.size();

    while (tryNumber > 0) {
    	Point temp = queue.poll();
        z_temp = temp.getZ();
        y_temp = temp.getY();
        x_temp = temp.getX();

        visited[z_temp][y_temp][x_temp] = true;
        tomatos[z_temp][y_temp][x_temp] = 1;

        for (int i = 0; i < 6; i++) {
             z_ttemp = z_temp + direction[i].getZ();
             y_ttemp = y_temp + direction[i].getY();
             x_ttemp = x_temp + direction[i].getX();

             if (x_ttemp < 0 || y_ttemp < 0 || z_ttemp < 0 ||
                 x_ttemp >= M || y_ttemp >= N || z_ttemp >= H) {
                 continue;
              }

              if (visited[z_ttemp][y_ttemp][x_ttemp] == false) {
                    queue.add(new Point(x_ttemp, y_ttemp, z_ttemp));
              }
         }
         tryNumber--;
     }
}

day에 대한 부분을 해결하기 위해, 해당 토마토가 있으면 좌표에 이전 좌표의 값 +1을 하여 방문 횟수를 표시하였다.

if (visited[nZ][nY][nX] == false && tomatos[nZ][nY][nX] == 0) {
	queue.add(new Point(nX, nY, nZ));
    tomatos[nZ][nY][nX] = tomatos[now.z][now.y][now.x] + 1;
}

아직 방문하지 않았고(visited[nZ][nY][nX] == false), 안익은 토마토(tomatos[nZ][nY][nX] == 0)라면 이전 좌표 기준에 1을 더해주는 것이다.

BFS가 다 끝나면, 토마토 배열을 돌면서 day에 해당하는 값 중 가장 큰 값에 -1을 하여 day를 구한다.

코드

package Algorithm.P7569;

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

public class P7569 {
    static StringBuilder sb;
    static int M, N, H;
    static boolean[][][] visited;
    static int[][][] tomatos;
    static Queue<Point> queue = new LinkedList<>();

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

    static int day = 0;

    public 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;
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P7569/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        tomatos = new int[H][N][M];
        visited = new boolean[H][N][M];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < M; k++) {
                    tomatos[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tomatos[i][j][k] == 1) {
                        queue.add(new Point(k, j, i));
                    }
                }
            }
        }

        while (!queue.isEmpty()) {
            Point now = queue.poll();
            visited[now.z][now.y][now.x] = true;

            for (int i = 0; i < 6; i++) {
                int nZ = now.z + dz[i];
                int nY = now.y + dy[i];
                int nX = now.x + dx[i];

                if (nX < 0 || nY < 0 || nZ < 0 ||
                        nX >= M || nY >= N || nZ >= H) {
                    continue;
                }

                if (visited[nZ][nY][nX] == false && tomatos[nZ][nY][nX] == 0) {
                    queue.add(new Point(nX, nY, nZ));
                    tomatos[nZ][nY][nX] = tomatos[now.z][now.y][now.x] + 1;
                }
            }
        }

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (tomatos[i][j][k] == 0) {
                        sb.append(-1);
                        System.out.println(sb);
                        System.exit(0);
                    }
                    day = Math.max(day, tomatos[i][j][k]);
                }
            }
        }

        sb.append(day - 1);

        System.out.println(sb);
    }
}