백준 7569번 : 토마토 (JAVA) 문제 풀이

https://www.acmicpc.net/problem/7569

7569번: 토마토

---

이 문제는 이전의 풀었던 7576번 토마토와 비슷한 문제이다.

이 문제에서의 다른 점은 토마토가 2차원 배열에 담기는게 아니라, 3차원 배열에 담기기 때문에 상,하,좌,우,앞,뒤까지 총 6번을 체크해줘야한다.

 

✏️ 문제

 

🔐 문제 해결

어려울 것이 없다. 이전과 동일한 방식으로 처리할 것이고, 그저 체크해야 할 곳이 2곳이 늘었다는 점 외에는 말이다.

토마토를 담기 위한 3차원 배열을 생성해준다. (날짜를 계산하기 위한 days 배열도 선언해준다.)

int[][][] tomatos = new int[H][N][M];	// 높이가 H이고, 가로가 N, 세로가 M
int[][][] days = new int[H][N][M];

 

큐에 좌표값을 넣어주기위해 2차원 토마토 문제에서는 Pair라는 클래스를 생성했지만, 이번에는 3차원이기 때문에 Triple이라는 클래스를 생성하도록 하겠다.

public static class Triple{
	int x, y, z;
    
    public Triple(int x, int y, int z){
    	this.x = x;
        this.y = y;
        this.z = z;
    }
    
    // getter,setter 생략
}

 

그리고 이전에는 dx, dy 좌표를 미리 선언해두었지만, 이번에는 dz 까지 미리 선언을 해두자.

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

 

이제 입력을 받음과 동시에 토마토가 익었으면 (값이 1이면) 큐에 넣어주고, days 배열의 값을 0으로 변경해준다.

만일, 0이거나 -1인 경우에는 days배열에 -1 값을 넣어준다.

for(int p=0; p<H; p++){
	for(int i=0; i<N; i++){
    	StringTokenizer st = new StringTokenizer(bf.readLine());
    	for(int j=0; j<M; j++){
            tomatos[p][i][j] = Integer.parseInt(st.nextToken());
            
            if(tomatos[p][i][j] == 1) {
            	qu.offer(new Triple(p, i, j));	// Triple이라는 클래스에 가로,세로,높이를 저장!
                days[p][i][j] = 0;	// 0으로 설정!
            }else{
            	days[p][i][j] = -1;	// -1으로 설정!
                if(tomatos[p][i][j] == 0){
                	notYet++;	// 안익은 토마토의 개수 증가
                }
            }
        }
    }
}

 

이제 가장 중요한 부분인 BFS 탐색을 하는 코드이다. 이전과 달라진 점은 없다.

// BFS!
while(!qu.isEmpty()){
    Triple t = qu.poll();
    
    for(int i = 0; i < 6; i++){		// 이제는 상하좌우앞뒤까지 탐색해준다.
        int nX = t.x + dx[i];
        int nY = t.y + dy[i];
        int nZ = t.z + dz[i];
        
        // 벽에 부딪히거나, 범위를 벗어나는 좌표는 PASS
        if(nX < 0 || nX >= N || nY < 0 || nY >= M || nZ < 0 || nZ >= H){
            continue;
        }
        
        // 토마토가 만약 없거나, 이미 방문한 토마토는 PASS
        if(tomatos[nZ][nX][nY] == -1 || days[nZ][nX][nY] != -1){
            continue;
        }
        
        // 익은 토마토와 인접한 익지 않은 토마토들을 큐에 넣어주고 익지 않은 토마토의 개수 -1 해준다.
        qu.offer(new Triple(nX, nY, nZ)); notYet--;
        days[nZ][nX][nY] = days[t.z][t.x][t.y] + 1;
        
        if(days[nZ][nX][nY] > result){
            result = days[nZ][nX][nY];
        }
    }
}

 

 

🖥 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      
      StringTokenizer st = new StringTokenizer(bf.readLine());
      int M = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());
      int H = Integer.parseInt(st.nextToken());
      int notYet = 0;
      int result = 0;
      
      int[][][] days = new int[H][N][M];        // 날짜를 계산하는 3차원배열
      int[][][] tomatos = new int[H][N][M];   // 토마토의 상태를 저장하는 3차원배열
      int[] dx = {1, 0, -1, 0, 0, 0};
      int[] dy = {0, 1, 0, -1, 0, 0};
      int[] dz = {0, 0, 0, 0, 1, -1};
      
      Queue<Triple> qu = new LinkedList<>();
      
      for(int p=0; p<H; p++){
          for(int i=0; i<N; i++){
              st = new StringTokenizer(bf.readLine());
              for(int j=0; j<M; j++){
                  tomatos[p][i][j] = Integer.parseInt(st.nextToken());
                  if(tomatos[p][i][j] == 1){
                      qu.offer(new Triple(i, j, p));
                      days[p][i][j] = 0;
                  }else{
                      days[p][i][j] = -1;
                      if(tomatos[p][i][j] == 0){
                          notYet++;
                      }
                  }
              }
          }
      }
      
      if(notYet == 0){
          System.out.print(0);
          System.exit(0);
      }
      
      while(!qu.isEmpty()){
          Triple t = qu.poll();
          
          for(int i = 0; i < 6; i++){
              int nX = t.x + dx[i];
              int nY = t.y + dy[i];
              int nZ = t.z + dz[i];
              
              if(nX < 0 || nX >= N || nY < 0 || nY >= M || nZ < 0 || nZ >= H){
                  continue;
              }
              
              if(tomatos[nZ][nX][nY] == -1 || days[nZ][nX][nY] != -1){
                  continue;
              }
              
              qu.offer(new Triple(nX, nY, nZ)); notYet--;
              days[nZ][nX][nY] = days[t.z][t.x][t.y] + 1;
              
              if(days[nZ][nX][nY] > result){
                  result = days[nZ][nX][nY];
              }
          }
      }
      
      if(notYet > 0){
          System.out.print(-1);
      }else{
          System.out.print(result);
      }
    }
    
    public static class Triple {
        int x,  y,  z;
        
        public Triple(int x, int y, int z){
            this.x = x;
            this.y = y;
            this.z = z;
        }
        
        public int getX(){
            return x;
        }
        
        public int getY(){
            return y;
        }
        
        public int getZ(){
            return z;
        }
        
        public void setX(int x){
            this.x = x;
        }
        
        public void setY(int y){
            this.y = y;
        }
        
        public void setZ(int z){
            this.z = z;
        }
    }
}