자바(백준) 7569 토마토-3차원(2021.05.25 수정)

package BFS;
 
import java.util.*;
 
public class Main {
    static int row,col,myeon;
    static int ad[][][];
    static boolean visit[][][];
    static Queue<Point> q = new LinkedList<>();
    static int count = 0;
    public static void main(String args[]){
        Scanner s = new Scanner(System.in);
 
        col = s.nextInt();
        row = s.nextInt();
        myeon = s.nextInt();
 
        ad = new int[myeon+1][row+1][col+1];
        visit = new boolean[myeon+1][row+1][col+1];
 
        for(int i = 1; i <= myeon; i++){
            for(int j = 1; j <= row; j++){
                for(int k = 1; k <= col; k++){
                    ad[i][j][k] = s.nextInt();
                    if(ad[i][j][k] == 1) {
                        q.offer(new Point(i, j, k, 0));
                        visit[i][j][k] = true;
                    }
                }
            }
        }
 
        bfs();
 
        for(int i = 1; i <= myeon; i++){
            for(int j = 1; j <= row; j++){
                for(int k = 1; k <= col; k++){
                    if(ad[i][j][k] == 0) {
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }
 
        System.out.println(count);
 
    }
    static void bfs(){
        int dx[] = {-1,1,0,0,0,0};
        int dy[] = {0,0,-1,1,0,0};
        int dz[] = {0,0,0,0,1,-1};
        while(!q.isEmpty()){
            Point point = q.poll();
            count = Math.max(count, point.depth);
            for(int i = 0; i < 6; i++){
                int rex = point.x + dx[i];
                int rey = point.y + dy[i];
                int rez = point.z + dz[i];
                if(isRangeTrue(rex,rey,rez) && ad[rex][rey][rez] == 0){
                    q.offer(new Point(rex,rey,rez,point.depth+1));
                    ad[rex][rey][rez] = 1;
                    visit[rex][rey][rez] = true;
                }
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y, int z){
        return x > 0 && x <= myeon && y > 0 && y <= row && z > 0 && z <= col;
    }
 
 
}
 
class Point{
    int x;
    int y;
    int z;
    int depth;
 
    public Point(int x, int y, int z, int depth){
        this.x = x;
        this.y = y;
        this.z = z;
        this.depth = depth;
    }
}

이 문제는 내가 직접 풀다가 못 풀어서 도움을 받아 푼 문제이다.

처음에는 런타임 에러가 뜨고, 수정하고 나선 메모리 초과가 났다. 메모리 초과가 왜 나는지에 대해 풀지 못해 이 문제를 해결하지 못한 것 같다. 생각해보면 3차원 사용, 6가지 방향까진 생각이 났는데 나머지 부분이 생각나지 않았다. 보면 ad 차원 배열에 수를 대입하면서 1인 수를 전역 큐에 offer하고, visit true를 해준다. 그리고 bfs를 parameter 없이 그냥 돌린다. bfs에는 Point형 변수를 선언하여 큐에서 poll하고, count 변수는 며칠이 걸리는지, point.depth와 count 중 최댓값을 비교한 것이다. 왜냐하면 만약 depth가 그대로 0이면 처음부터 익을 토마토가 없다는 뜻이다. 그리고 depth는 날짜를 의미하고 점점 갈수록 1씩 늘어나는 것이, Point형 자료가 한 개씩 늘어날 때마다 1일씩 늘어나기 때문이다. 

 

 

---

오답 노트 & 새로 알게 된 점

처음에 이 문제를 풀 때 index의 규칙성을 이용하여 이차원 배열로 풀어보려고 시도했다. 

입력할 때 만약 1이 입력되면 그 좌표에서 행 크기 만큼 더해주거나 빼주면 될 줄 알았지만, 더하고 빼주는 데에서 문제가 생겼다. 그래서 3차원 배열을 이용하여 풀었다. 3차원 배열을 사용할 때, 높이는 for문의 첫 번째에 시작해주어야 한다. 그 부분에서 실수했다. 그리고 dz [] 배열을 선언하는 데에 있어서 위, 아래를 어떻게 나타내야 하지 라는 생각을 했다. 이번 문제를 통해 그러한 실수와 삼차원을 이용할 때, z를 어떻게 나타낼 수 있는지 알게 되었다.

 

package BFS;
 
//BOJ 7569 토마토
 
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int row, height, col;
    static Queue<Tomatopoint> q = new ArrayDeque<>();
    static int arr[][][];
    static boolean visit[][][];
    static int result = Integer.MIN_VALUE;
    public static void main(String args[]){
        //3차원으로 풀지 않고 해결할 수 있을 것 같아
        //height만큼 행을 곱해줘서 이차원 배열로 나타내고
        //value가 1인 index는 행렬 범위에 벗어나지 않게
        //열은 똑같고 해당 행 index +- 행 크기 만큼 모두 1로 나타내주기
        //실패 --> 나중에 2차원으로 풀어보자
 
        //그러면 삼차원 배열로 하기
        Scanner s = new Scanner(System.in);
 
        col = s.nextInt();
        row = s.nextInt();
        height = s.nextInt();
 
        arr= new int[row][col][height];
        visit = new boolean[row][col][height];
 
        //이 부분에서 실수함
        //height 부터 for문을 만들어야함.
        for(int k = 0; k < height; k++){
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    arr[i][j][k] = s.nextInt();
                    if(arr[i][j][k] == 1){
                        q.offer(new Tomatopoint(i, j, k ,0));
                    }
                }
            }
        }
        bfs();
 
        for(int k = 0; k < height; k++){
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    if(arr[i][j][k] == 0) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
        }
        System.out.println(result);
    }
 
    static void bfs(){
        int dx[] = {-1,1,0,0,0,0};
        int dy[] = {0,0,1,-1,0,0};
        int dz[] = {0,0,0,0,1,-1}; //z를 캐치 못함
        while(!q.isEmpty()){
            Tomatopoint tp = q.poll();
            int x = tp.x;
            int y = tp.y;
            int z = tp.z;
            int count = tp.count;
            result = Math.max(result, count);
            visit[x][y][z] = true;
            for(int i = 0; i < 6; i++) {
                int X = x + dx[i];
                int Y = y + dy[i];
                int Z = z + dz[i];
 
                if (!isRangeTrue(X, Y, Z)) continue;
                if (visit[X][Y][Z]) continue;
 
                if (arr[X][Y][Z] == 0) {
                    arr[X][Y][Z] = 1;
                    q.offer(new Tomatopoint(X, Y, Z, count + 1));
                    visit[X][Y][Z] = true;
                }
            }
        }
    }
    static boolean isRangeTrue(int x, int y, int z){
        return x >= 0 && x < row && y >= 0 && y < col && z >= 0 & z < height;
    }
}
 
class Tomatopoint{
    int x, y, count, z;
 
    Tomatopoint(int x, int y, int z, int count){
        this.x  = x;
        this.y  = y;
        this.count = count;
        this.z = z;
    }
}