[Day12]JAVA- 백준 토마토 (7569번) BFS 활용

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

 

백준 7569번 문제는 BFS 를 활용해서 풀 수 있다. 

3차원 배열이 나와서 당황할 수 있지만 침착하게 문제의 규칙을 찾으면 된다. 

 

여기서 규칙은 토마토가 상, 하 , 좌 , 우 , 앞, 뒤 로 영향을 준다는 것이다. 

3차원 배열이여서 이해가 어려울 수 있는데

 

콘서트 장이라고 생각해보면 

상,하(H) 는 1층,2층..  을 나타내는 것이고 

좌,우(M) 는 양 옆 을 나타내는 것이고 , 2차원에서는 열이라고 한다. 

앞,뒤(N) 는 앞줄 , 뒷줄을 나타내는 것이고, 2차원에서는 행이라고 한다. 

 

콘서트장 가면 어떻게 앉는가? 1층 앞줄부터 하나씩 앉지 않는다.  쉽게 생각해서 1층 앞줄 부터 자리를 채워간다고 생각하면 된다. 

 

*혼자 힘으로 풀고 싶으면 힌트만 확인하기*
<힌트> 
1. 토마토상자를 3차원 배열이라고 생각하고 토마토의 상태를 입력 받는다.
2. 익은 토마토는 Queue 안에 넣는다. 
3. 익은 토마토 기준으로 상,하,좌,우,앞,뒤  의 토마토의 상태를 확인한다.
4. 안익은 토마토가 있으면 익힌다. 익힌 토마토를 큐에 넣는다. (최종일자를 구하는 것이기 때문에 앞전의 값에 +1 을 하며 일자 늘려간다.)
5. 큐가 빈 값이 될때까지 반복한다.
6. 최종적으로 토마토 상태 확인한다.
7. 0 이 있으면 못익힌 토마토가 있는 것이므로 -1 출력
8. 최대 값을 구한다. 
9. 최대 값이 1 이면 처음부터 다 익은 토마토 이므로 0 출력

 

 

---

토마토 상자를 배열이라고 생각하고 1층(H) 앞줄(N) 부터 한칸씩(M) 토마토를 넣으면 된다.  

 int[][][] tomatoBox = new int[H+1][N+1][M+1];

 

토마토 상태를 입력받는 것도 , 동일한 순서로 넣는다. 

토마토를 입력 받을때 , 익은 토마토는 Queue 안에 넣는다. (익은 토마토 기준으로 BFS돌릴 것이다..)

//토마토 입력받기 
for(int i=1;i<=H;i++)  //층
{
  for(int j=1;j<=N;j++) //행
  {   
  	st = new StringTokenizer(br.readLine());
    for(int k=1;k<=M;k++) //열
    {
        tomatoBox[i][j][k] = Integer.parseInt(st.nextToken());
            //익은 토마토는 Queue 에 넣기 
            if(tomatoBox[i][j][k] == 1)
                que.add(new pointHNM(i,j,k));
    }
  }
}

 

상, 하 , 좌 , 우 , 앞, 뒤 로 영향을 주는 것은 

상,하(H) 가 -1 , +1 한 층씩 움직이고

좌,우(M) 가 -1 , +1 한 열씩 움직이고

앞,뒤(N) 가 -1 , +1 한 행씩 움직이는 것이다. 

 

이를 heightArr , rowArr, colArr 에 표시하는 것이다. 

int[] heightArr  = {-1,0,1,0,0,0};
int[] rowArr     = {0,1,0,-1,0,0};
int[] colArr     = {0,0,0,0,1,-1};

 

 

토마토 익히는 것은 BFS를 활용해서 상,하,좌,우,앞,뒤 6번의 경우의 토마토 상태를 확인할때는

1. 토마토 상자의 범위를 벗어나지 않게 체크 > 범위를 벗어나면 확인하지 않는다.
2. 익지 않은 토마토인지 확인 > 익지 않은 토마토면 익힌다. (익힘은 일자로 표시한다.)

 

확인 할 수 있는 모든 토마토를 돌았으면 3가지 경우를 확인한다.

1. 안익은 토마토가 있는지 >  -1 출력
2. 다 익었으면 며칠이 걸렸는지 > 익을 때까지 걸린 시간 출력
3. 처음부터 다 익힌 토마토 상자였는지 > 0 출력 

 

public static int BFS()
{
  while(!que.isEmpty())
  {
    //익은 토마토 
    pointHNM point = que.poll(); 
    int nowHeight = point.height;
    int nowRow = point.row;
    int nowCol = point.col;

    //상하좌우앞뒤로 토마토 익히기
    for(int i=0;i<6;i++)
    {
      int nextHeight = nowHeight + heightArr[i];
      int nextRow = nowRow + rowArr[i];
      int nextCol = nowCol+ colArr[i];

      if(checkTomato(nextHeight, nextRow, nextCol))
      { 
        //익힌 일자 추가 
        tomatoBox[nextHeight][nextRow][nextCol] = tomatoBox[nowHeight][nowRow][nowCol]+1;
        que.add(new pointHNM(nextHeight, nextRow, nextCol)); 
      }
    }
  }

  int answer = Integer.MIN_VALUE;

  //최종적으로 토마토 익었는지 확인      
  for(int i=1;i<=H;i++)
  {
    for(int j=1;j<=N;j++)
    {        
      for(int k=1;k<=M;k++)
      {            

          // 0 이 있으면 안익은 토마토 
          if(tomatoBox[i][j][k] == 0)
          {
            return -1;
          }
          else
          {               
            answer = Math.max(answer,tomatoBox[i][j][k]-1);
          }
      }
    }
  }

 

 

*최종코드 

// M :가로(열) , N: 세로(행) , H : 높이
// 1 : 익은 토마토 
// 0 : 안익은 토마토
// -1 : 없는 토마토 
import java.util.*;
import java.io.*;
public class Main{
  static int M , N , H;
  static int[][][] tomatoBox;
  static Queue<pointHNM> que = new LinkedList<>();    
  static int[] heightArr  = {-1,0,1,0,0,0};
  static int[] rowArr     = {0,1,0,-1,0,0};
  static int[] colArr     = {0,0,0,0,1,-1};

  public static void main(String[] args) throws IOException
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    M = Integer.parseInt(st.nextToken()); //가로(열)
    N = Integer.parseInt(st.nextToken()); //세로(행)
    H = Integer.parseInt(st.nextToken()); //높이(층)

    //상자 크기의 배열 생성
    tomatoBox = new int[H+1][N+1][M+1];

    //토마토 입력받기 
    for(int i=1;i<=H;i++)
    {
      for(int j=1;j<=N;j++)
      {
        st = new StringTokenizer(br.readLine());
        for(int k=1;k<=M;k++)
        {
            tomatoBox[i][j][k] = Integer.parseInt(st.nextToken());
            //익은 토마토는 Queue 에 넣기 
            if(tomatoBox[i][j][k] == 1)
                que.add(new pointHNM(i,j,k));
        }
      }
    }
    System.out.println(BFS());
  }

  //BFS 토마토 익히기 
  public static int BFS()
  {
      while(!que.isEmpty())
      {
        //익은 토마토 
        pointHNM point = que.poll(); 
        int nowHeight = point.height;
        int nowRow = point.row;
        int nowCol = point.col;

        //상하좌우앞뒤로 토마토 익히기
        for(int i=0;i<6;i++)
        {
          int nextHeight = nowHeight + heightArr[i];
          int nextRow = nowRow + rowArr[i];
          int nextCol = nowCol+ colArr[i];

          if(checkTomato(nextHeight, nextRow, nextCol))
          { 
            //익힌 일자 추가 
            tomatoBox[nextHeight][nextRow][nextCol] = tomatoBox[nowHeight][nowRow][nowCol]+1;
            que.add(new pointHNM(nextHeight, nextRow, nextCol)); 
          }
        }
      }

      int answer = Integer.MIN_VALUE;
      
      //최종적으로 토마토 익었는지 확인      
      for(int i=1;i<=H;i++)
      {
        for(int j=1;j<=N;j++)
        {        
          for(int k=1;k<=M;k++)
          { 
              // 0 이 있으면 안익은 토마토 
              if(tomatoBox[i][j][k] == 0)
              {
                return -1;
              }
              else
              {               
                answer = Math.max(answer,tomatoBox[i][j][k]-1);
              }
          }
        }
      }

      //최대값이 1 은 처음부터 다 익은 토마토들 
      if(answer == 1 )
          answer = 0;

      return answer;
  }

  public static Boolean checkTomato(int h , int r , int c)
  {
    //토마토가 상자 범위안에 있는지 확인
    if(h<1 || h>H || r<1 || r>N || c<1 || c>M )
      return false;
    else if(tomatoBox[h][r][c] == 0)
    {
      return true;
    }
    return false;
  }
}

class pointHNM
{
  int height;
  int row;
  int col;

  public pointHNM(int h , int r, int c)
  {
    this.height = h;
    this.row = r;
    this.col = c;
  }
}

 

 

BFS , DFS 문제는 어느정도 방식에 대해서 이해를 완료하면 다음은 많은 문제를 풀면서 규칙을 찾는 연습을 하는게 중요한거 같다.