[240330] 알고리즘 리부트 42일차 - 프로그래머스 게임 맵 최단거리 자바

import java.util.*;

class Solution {
    public static Deque<Position> dq;
    public static int dist[][];
    public static int n, m;
    public static class Position{
        int r;
        int c;
        public Position(int x, int y){
            this.r = x;
            this.c = y;       
        }
    }
    public int solution(int[][] maps) {
        int answer = -1;
        
        n = maps.length;
        m = maps[0].length;
        
        dist = new int[n][m];
        
        dist[0][0] = 1;
        dq = new ArrayDeque<Position>();
        
        dq.add(new Position(0, 0));
        
        
        int nr;
        int nc;
        
        while(!dq.isEmpty()){
            int [][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
            
            Position curr = dq.poll();
            
            for(int d = 0; d < 4; d++){
                nr = curr.r + drc[d][0];
                nc = curr.c + drc[d][1];
                
                if(nr < 0||nc < 0|| nr > n-1 || nc > m-1 ||
                   dist[nr][nc]!=0 || maps [nr][nc] == 0) continue; 
                                
                dq.add(new Position(nr, nc));
                dist[nr][nc] = dist[curr.r][curr.c]+1;
            }            
        }     
        
        answer = dist[n-1][m-1]!=0 ? dist[n-1][m-1] : -1;
        return answer;
    }
}

 

[효율성 테스트 실패 코드]

import java.util.*;

class Solution {
    public static Deque<Position> dq;
    public static boolean visited[][];
    public static int n, m;
    public static class Position{
        int r;
        int c;
        int dist;
        public Position(int x, int y, int d){
            this.r = x;
            this.c = y;       
            this.dist = d;
        }
    }
    public int solution(int[][] maps) {
        int answer = -1;
        
        n = maps.length;
        m = maps[0].length;
        
        visited = new boolean[n][m];
        dq = new ArrayDeque<Position>();
        
        dq.add(new Position(0, 0, 1));
        
        int nr;
        int nc;
        
        while(!dq.isEmpty()){
            int [][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
            
            Position curr = dq.poll();
            
            if(curr.r == n-1 && curr.c == m-1){
                answer = curr.dist;
                break;
            }
                     
            visited[curr.r][curr.c] = true;
            
            for(int d = 0; d < 4; d++){
                nr = curr.r + drc[d][0];
                nc = curr.c + drc[d][1];
                
                if(nr < 0||nc < 0|| nr > n-1 || nc > m-1 ||
                   visited[nr][nc] || maps [nr][nc] == 0) continue; 
                
               
                dq.add(new Position(nr, nc, curr.dist + 1));                            
            }            
        }        
        return answer;
    }
}