[백준 알고리즘] 2178번 미로탐색 with JAVA (메모리 초과)

문제는 전형적인 bfs문제인 미로 탐색이다.  큐를 통해서 배열을 한번씩 방문하면서 거리계산을하고 마지막

N,M으로 도착할시에 출력하면 최단거리로 출력이된다. 하지만, 방문표시에 대한 코드 한줄때문에 계속 메모리 초과가 나서 고생했다. 수정내용은 코드에 주석처리 해놓았다. 

 

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


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

        

}

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[0]);
        int arrayY = Integer.parseInt(arrayXY[1]);

        int[][] painting = new int[arrayX][arrayY];
        int[][] visit = new int[arrayX][arrayY];
        for(int i=0;i<arrayX;i++){
            String[] data = bf.readLine().split("");
            for(int j=0;j<arrayY;j++){
   
                painting[i][j] = Integer.parseInt(data[j]);
 
            }

        }

        int smalldist = 0;

        Queue<Pair> bfs = new LinkedList<>();
        bfs.add(new Pair(0,0,1));
        visit[0][0] = 1;
        while(!bfs.isEmpty()){
            Pair pair = bfs.poll();
            //메모리 초과
            //visit[pair.x][pair.y] = 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 ||painting[aX][aY]!=1){
                    continue;
                }
                
                visit[aX][aY] = 1;

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

            if((pair.x==(arrayX-1))&&(pair.y==(arrayY-1))){
                if(smalldist ==0){
                    smalldist=pair.dist;
                    bfs.clear();
                    break;
                }
            }
            
            
        }
        
        System.out.println(smalldist);
        
        
    }

}