알고리즘33 :: BOJ_1261_알고스팟

이 문제에 대한 접근은 다음과 같습니다.

우선순위 큐를 쓰되, 최소 힙으로 잡으셔야 합니다. 

왜냐하면, 맵을 순회하면서 벽이 있다면 벽을 부순 값을 dist에 저장하는데 

이때 dist 값이 큐에 들어가서 최대 힙으로 잡히면 맨 밑부터 찾아봐야하는 일이 발생하게 됩니다. => 메모리 초과의 원인 

그외에는 최소값을 갱신시켜주기 위한 조건만 넣어주신다면 일반적인 BFS 와 다를것이 없습니다. 

public class Main {
 
    private static int[][] map;
    private static int m, n;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
 
    private static int[][] dist; 
    private static class Pair implements Comparable<Pair>{
        int x;
        int y;
        int value;
        Pair(int x, int y, int value){
            this.x = x;
            this.y = y;
            this.value = value;
        }
        @Override
        public int compareTo(Pair o) {
            // TODO Auto-generated method stub
            return this.value - o.value;
        }
 
    }
    private static int ans ;
    private static void BFS(int xx, int yy) {
 
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(0,0,0));
 
        dist[xx][yy] = 0;
        while(!pq.isEmpty()) {
 
            Pair z = pq.remove();
 
            int x = z.x;
            int y = z.y;
            for(int i=0; i<4; i++) {
 
                int ddx = x + dx[i];
                int ddy = y + dy[i];
 
                if(ddx<0 || ddx>=n || ddy<0 || ddy>=m) continue;
 
                if(map[ddx][ddy] == 1) {
                    if(dist[ddx][ddy] > dist[x][y]+1) {
                        dist[ddx][ddy] = dist[x][y] +1;
                        pq.add(new Pair(ddx, ddy,dist[ddx][ddy]));
                    }
                }else if( map[ddx][ddy] == 0) {
                    if(dist[ddx][ddy]>dist[x][y]) {
                    dist[ddx][ddy] = dist[x][y];
                    pq.add(new Pair(ddx, ddy, dist[ddx][ddy]));
                    }
                }
 
            }
 
        }
 
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
 
        map = new int[n][m];
 
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(str.substring(j, j+1));
            }
        }
        //System.out.println("debug--");
        dist = new int[n][m];
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
 
        BFS(0,0);
        System.out.println(dist[n-1][m-1]);
    }
 
}