[문제풀이] 08-12. 토마토

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0812. 토마토(BFS)

🗒️ 문제

🎈 나의 풀이

	private static Queue<RipeTomato> Q = new LinkedList<>();
    private static class RipeTomato {
        int x, y;

        public RipeTomato(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void ripen(int[][] box) {
            if(x-1>=0 && box[x-1][y] == 0) {
                box[x-1][y] = 1;
                Q.add(new RipeTomato(x-1, y));
            }
            if(x+1<box.length && box[x+1][y] == 0) {
                box[x+1][y] = 1;
                Q.add(new RipeTomato(x+1, y));
            }
            if(y-1>=0 && box[x][y-1] == 0) {
                box[x][y-1] = 1;
                Q.add(new RipeTomato(x, y-1));
            }
            if(y+1<box[0].length && box[x][y+1] == 0) {
                box[x][y+1] = 1;
                Q.add(new RipeTomato(x, y+1));
            }
        }
    }
    private static int solution(int[][] box) {
        int answer = 0;

        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Q.poll().ripen(box);
            }
            answer++;
        }

        for(int i=0; i<box.length; i++){
            for(int j=0; j<box[0].length; j++) {
                if(box[i][j] == 0) return -1;
            }
        }

        return answer - 1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] box = new int[m][n];

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++)
            {
                box[i][j] = sc.nextInt();
                if(box[i][j] == 1) Q.add(new RipeTomato(i, j));
            }
        }

        System.out.println(solution(box));
    }

🖍️ 강의 풀이

  class Point{
      public int x, y;
      Point(int x, int y){
          this.x=x;
          this.y=y;
      }
  }
  class Main {
      static int[] dx={-1, 0, 1, 0};
      static int[] dy={0, 1, 0, -1};
      static int[][] board, dis;
      static int n, m;
      static Queue<Point> Q=new LinkedList<>();
      public void BFS(){
          while(!Q.isEmpty()){
              Point tmp=Q.poll();
              for(int i=0; i<4; i++){
                  int nx=tmp.x+dx[i];
                  int ny=tmp.y+dy[i];
                  if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0){
                      board[nx][ny]=1;
                      Q.offer(new Point(nx, ny));
                      dis[nx][ny]=dis[tmp.x][tmp.y]+1;
                  }
              }
          }	
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          m=kb.nextInt();
          n=kb.nextInt();
          board=new int[n][m];
          dis=new int[n][m];
          for(int i=0; i<n; i++){
              for(int j=0; j<m; j++){
                  board[i][j]=kb.nextInt();
                  if(board[i][j]==1) Q.offer(new Point(i, j));
              }
          }
          T.BFS();
          boolean flag=true;
          int answer=Integer.MIN_VALUE;
          for(int i=0; i<n; i++){
              for(int j=0; j<m; j++){
                  if(board[i][j]==0) flag=false;
              }
          }
          if(flag){
              for(int i=0; i<n; i++){
                  for(int j=0; j<m; j++){
                      answer=Math.max(answer, dis[i][j]);
                  }
              }
              System.out.println(answer);
          }
          else System.out.println(-1);
      }
  }

💬 짚어가기

해당 문제는 BFS를 이용하여 풀 수 있으며, 이전에 풀이한 미로의 최단거리찾기 문제와
로직이 거의 동일하다. 이번에는 목표 지점에 도착하여 종료하는 것이 아닌, while문이
더 이상 돌지 않을 때까지(모든 토마토가 익을 때까지) 방치해두면 된다.

나의 풀이에서는 RipeTomato라는 클래스를 두어 익은 토마토의 위치를 보관할 수 있도록
하였고, ripen 메소드를 두어 상하좌우에 존재하는 안익은 토마토를 찾도록 하는데,
이번에는 찾은 후에 방문 표시와 더불어 해당 토마토를 Queue에 집어 넣도록 하였다.
( BFS에서의 코드가 간결해졌다! 대신 탐색을 토마토 객체가 수행하는 꼴이 되버렸네.. )

처음 토마토 상태를 입력 받을 때 익은 토마토는 Queue에 집어 넣고, 이후 BFS를 수행한다.
더 이상 Queue에 넣을 토마토가 없을 때 지금까지 순회한 횟수를 반환하여 문제를 해결했다.
강의 코드 또한 구조는 다르나 동일한 로직으로 수행된다.