백준 7569 토마토 3D 알고리즘 문제 자바 JAVA 풀이 해설 리뷰

 

 

 

 

백준 7569 토마토 문제는 기존 토마토 문제와 동일하지만 3D로 만들어진 토마토 틀에서 토마토가 익는 날짜를 구하는 문제다. BFS 알고리즘을 사용하지만 좌표값이 2D에서 3D로 늘어났을 뿐이다. BFS 알고리즘을 까먹었거나 익숙하지 않다면 아래 글을 꼭 참고 하고 오길 바란다.

 

BFS 알고리즘

 

백준 7576 토마토 알고리즘 문제 자바 JAVA CODE

 

백준 1012 유기농 배추 알고리즘 자바 JAVA

 

백준 2178 미로 탐색 알고리즘 자바 JAVA 풀이

 

 

 

 

백준 7569는 기존 문제와 다르게 3D로 풀어야 하는문제다.

좌표값을 X,Y에 더해서 Z 값을 구해줘야 한다.

 

 

좌표값 변수형으로 Point 클래스를 사용했었는데, 

이번에는 아예 클래스를 새로 만들어서 사용했다.

 

class PointXYZ{
    int x;
    int y;
    int z;
    public PointXYZ(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;

    }
}

 

 

 

3차원 배열의 경우 인자를 전달하는 순서는 

Z 좌표, Y 좌표, X 좌표 순으로 전달하면 된다.

int[][][] array = new int[Z][Y][X];

 

for 문을 순회하는 순서도 배열 정의순서와 동일하게

Z,Y,X 순서로 순회하게 된다.

 

for(int k=0; k<H; k++){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            matrix[k][i][j] = in.nextInt();
        }
    }        
}

 

 

 

좌표 값을 표시하기 위해서 3개의 배열을 통해

6개 인자를 뽑아내었고, 새로운 좌표값을 만드는데

사용했다.

 

int[] NEW_X = {-1,1,0,0,0,0};        
int[] NEW_Y = {0,0,-1,1,0,0};
int[] NEW_Z = {0,0,0,0,-1,1};

 

3차원 배열을 BFS 알고리즘으로 토마토가 

익는 날짜는 COUNTER 배열을 통해서

노드 탐색 순서를 COUNTING 하면 된다.

 

출력값을 보면 최초 토마토가 존재하는 좌표로

부터 상하좌우로 1씩 증가하는 것을 볼 수 있다.

BFS 탐색 알고리즘으로 카운팅한 결과이고,

최대 카운팅 값을 출력하면 토마토가 익기 위해

필요한 날짜가 출력된다.

 

입력값

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

 

 

출력값

54345
43234
54345
43234
32123
43234

 

 

 

백준 7569 토마토 3D 자바 JAVA CODE

/*
    Owner : Developer Blog
    Title : 토마토 3D 문제
    Algorithm : BFS 알고리즘
    Date : 2022-03-11
*/


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


// X, Y, Z 좌표값
class PointXYZ{
    int x;
    int y;
    int z;
    public PointXYZ(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;

    }
}


public class A_7569 {
    private static int M,N,H;
    private static int[][][] matrix;
    private static int[][][] counter;
    private static boolean[][][] visit;

    private static Queue<PointXYZ> queue = new LinkedList<PointXYZ>();

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

        M = in.nextInt();
        N = in.nextInt();
        H = in.nextInt();
        matrix = new int[H+1][N+1][M+1];
        counter = new int[H+1][N+1][M+1];
        visit = new boolean[H+1][N+1][M+1];
        
        
        // 배열값을 입력받는다.
        for(int k=0; k<H; k++){
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    matrix[k][i][j] = in.nextInt();
                }
            }        
        }

        

        // 최초 배열에서 1을 찾는다.
        for(int k=0; k<H; k++){
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                	// 토마토가 존재하면 큐(Queue)에 추가한다.
                    if(matrix[k][i][j]==1){
                        queue.add(new PointXYZ(j,i,k));
                        counter[k][i][j]=1;
                        
                     // 토마토가 존재하지 않으면 -1로 표시한다.
                    }else if(matrix[k][i][j]==-1){
                        counter[k][i][j]=-1;
                    }
                }
            }
        }

		System.out.println(bfs());
       

    }

    private static int bfs(){
        int[] NEW_X = {-1,1,0,0,0,0};        
        int[] NEW_Y = {0,0,-1,1,0,0};
        int[] NEW_Z = {0,0,0,0,-1,1};

        while(!queue.isEmpty()){
            PointXYZ temp = queue.poll();

			// X, Y, Z 6번 반복문 순회
            for(int i=0; i<6; i++){
                int new_x = temp.x+NEW_X[i];
                int new_y = temp.y+NEW_Y[i];
                int new_z = temp.z+NEW_Z[i];
                
                // 주어진 좌표값에서 익지 않은 토마토를 찾는 BFS 알고리즘
                if(new_x>=0 && new_y>=0 && new_z>=0 && new_x<M && new_y<N && new_z<H){
                    if(matrix[new_z][new_y][new_x]==0 && !visit[new_z][new_y][new_x]){
                        queue.add(new PointXYZ(new_x, new_y,new_z));
                        visit[new_z][new_y][new_x] = true;
                        counter[new_z][new_y][new_x] = counter[temp.z][temp.y][temp.x]+1;
                    }
                }
            }
        }
        
        // COUNTER에서 MAX값을 탐색
        int max = 0;
        for(int k=0; k<H; k++){
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(counter[k][i][j]==0) return -1;
                    max = Math.max(max, counter[k][i][j]);
                }
            }
        }
        return max-1;       

    }

}

 

백준 7569 토마토 자바 JAVA 제출결과

 

 

 

추천 콘텐츠

 

백준 알고리즘 2630번 분할정복 색종이 만들기 자바 JAVA

 

백준 1260 DFS와 BFS 알고리즘 자바 JAVA

 

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘 리뷰

 

백준 알고리즘 2798번 블랙잭 문제 JAVA

 

알고리즘 설계기법