[백준 알고리즘] 7576번 토마토 with JAVA (메모리 초과)

전형적인 BFS 문제이다.

 

하루가 지날때마다 토마토는 익고 박스안에 토마토들이 전부다 익으면 그 날을 계산하여 출력하는거다.

 

1. 입력된 토마토박스에서 익은 토마토를 찾아서 그 토마토에 위치를 저장해두는 클래스, 그리고 그 클래스를 담는 queue<bfs>를 생성한다.

 

2. 큐가 빌때까지 루프를 돌리고 queue에서 나온 토마토 좌표에서 상하좌우를 계산한후 방문하지 않고 익지않은 토마토를 다시 위치 클래스로 만들고 그 클래스를 queue에 담는다. 또한 상하좌우를 계산할때 하루가 지날때마다 익는다고 하였으니, 위치 클래스안에 변수 ripe를 만들어서 1씩 더해주자

 

3.큐가 다비면 더이상 방문할 토마토가 없는것이고, 다시 토마토 박스를 점검하여 배열에 0이 존재하면 -1를 출력하고 그렇지 않다면 몇일이 지나면 익는지에 대한 최소 일을 출력한다. 아래는 그 코드이다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


class Pair {
    public int x,y,ripe;
        Pair(int x,int y,int ripe){
            this.x = x;
            this.y = y;
            this.ripe = ripe;
        }

        

}

public class Main {
    

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

    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] arrayXY = bf.readLine().split(" ");
        int arrayX = Integer.parseInt(arrayXY[1]);
        int arrayY = Integer.parseInt(arrayXY[0]);

        int[][] tomato = new int[arrayX][arrayY];
        int[][] visit = new int[arrayX][arrayY];
        Queue<Pair> bfs = new LinkedList<>();
        for(int i=0;i<arrayX;i++){
            String[] data = bf.readLine().split(" ");
            for(int j=0;j<arrayY;j++){
                int k = Integer.parseInt(data[j]);
                tomato[i][j] = k;
                
                if(k==1){
                    bfs.add(new Pair(i,j,0));
                    visit[i][j] = 1;
                }else{
                    visit[i][j] = 0;
                }
            }

        }

        int smalldist = 0;
        

        
        while(!bfs.isEmpty()){
            Pair pair = bfs.poll();
            //메모리 초과
            //visit[aX][aY] = 1;
            for(int i=0;i<4;i++){
                int aX = pair.x+dx[i];
                int aY = pair.y+dy[i];
                
                if(aX<0 || aY<0 || aX>=arrayX||aY>=arrayY){
                    continue;
                }
                if(visit[aX][aY] ==1 ||tomato[aX][aY]!=0){
                    continue;
                }
                
                visit[aX][aY] = 1;
                tomato[aX][aY] = 1;
                bfs.add(new Pair(aX,aY,pair.ripe+1));
                
            }
            smalldist = pair.ripe;
            
            
            
        }
        for(int i=0;i<arrayX;i++){
          
            for(int j=0;j<arrayY;j++){
                if(tomato[i][j]==0){
                    smalldist = -1;
                    System.out.println(smalldist);
                    return;
                }
                
            }

        }

        System.out.println(smalldist);
        
        
    }

}

 

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

class Pair {

    public int x,y,ripe;

        Pair(int x,int y,int ripe){

            this.x = x;

            this.y = y;

            this.ripe = ripe;

        }

       

}

public class Main {

   

    final static int dx[] = {1,-1,0,0};

    final static int dy[] = {0,0,1,-1};

   

    public static void main(String[] args) throws Exception {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] arrayXY = bf.readLine().split(" ");

        int arrayX = Integer.parseInt(arrayXY[1]);

        int arrayY = Integer.parseInt(arrayXY[0]);

        int[][] tomato = new int[arrayX][arrayY];

        int[][] visit = new int[arrayX][arrayY];

        Queue<Pair> bfs = new LinkedList<>();

        for(int i=0;i<arrayX;i++){

            String[] data = bf.readLine().split(" ");

            for(int j=0;j<arrayY;j++){

                int k = Integer.parseInt(data[j]);

                tomato[i][j] = k;

               

                if(k==1){

                    bfs.add(new Pair(i,j,0));

                    visit[i][j] = 1;

                }else{

                    visit[i][j] = 0;

                }

            }

        }

        int smalldist = 0;

       

       

        while(!bfs.isEmpty()){

            Pair pair = bfs.poll();

       

            for(int i=0;i<4;i++){

                int aX = pair.x+dx[i];

                int aY = pair.y+dy[i];

               

                if(aX<0 || aY<0 || aX>=arrayX||aY>=arrayY){

                    continue;

                }

                if(visit[aX][aY] ==1 ||tomato[aX][aY]!=0){

                    continue;

                }

               

                visit[aX][aY] = 1;

                tomato[aX][aY] = 1;

                bfs.add(new Pair(aX,aY,pair.ripe+1));

               

            }

            smalldist = pair.ripe;

           

           

           

        }

        for(int i=0;i<arrayX;i++){

         

            for(int j=0;j<arrayY;j++){

                if(tomato[i][j]==0){

                    smalldist = -1;

                    System.out.println(smalldist);

                    return;

                }

               

            }

        }

        System.out.println(smalldist);

       

       

    }

}