문제

입력

출력

예제

idea 및 정리

최단거리 문제이기 때문에 BFS를 이용하여 풀었다.
출발지점은 1,1 끝나는 지점은 n,m 으로 설정
최단거리 탐색을 하며 n,m에 도착을 했을 때 몇번 이동하였는지 출력

처음에는 방문 여부를 측정하기 위해 visited를 사용하였으나 효율성에서 자꾸 문제가 있어 visited를 없애고 방문 한 부분의 배열을 0으로 설정하여 다시 방문하지 못하도록 하였다.
하지만 그래도 효율성에 문제가 발생하여 원인을 계속해서 파악해 보니 전혀 예상치도 못한 print문 때문에 문제가 발생한 것을 알게되었다. 주석 처리하니까 바로 성공..
그래서 효율성 문제가 vistied때문인지 print때문인지 둘 다 때문인지 잘 모르겠다..

그래도 코테를 위해 프로그래머스 적응하는 중인데 print문 없애고 제출하기.. 꿀팁 확인..

Code

//BFS 최단 거리 문제
import java.util.*;
class Solution {
    static Queue<int[]> queue = new ArrayDeque<>();  
    static int x=0, y=0;    
    
    public int solution(int[][] maps) {
        
        y = maps.length;
        x = maps[0].length;
        
        // visited = new boolean[y][x];
        // array = new int[y][x];
        // for(int i=0;i<y;i++){
        //     for(int j=0;j<x;j++){
        //         array[i][j]=maps[i][j];
        //         if(array[i][j]==0)
        //             visited[i][j]=true;
        //     }
        // }
        queue.add(new int[] {0,0,1});
        // visited[0][0]=true;       
        
        return bfs(maps);
    }
    
    public static int bfs(int[][] maps){
        int[] di={1,0,-1,0};
        int[] dj={0,1,0,-1};
        int dx=0,dy=0;
        int[] cur= new int[3];
        int num=0;
        int min = Integer.MAX_VALUE;
        
        while(!queue.isEmpty()){
            cur=queue.poll();
            for(int i=0;i<4;i++){
                dy=cur[0]+di[i];
                dx=cur[1]+dj[i];
                num = cur[2];
            
               if(dx<0||dx>=x||dy<0||dy>=y||maps[dy][dx]==0) continue; 
                
                //System.out.println(dy+1+" "+(dx+1)+" "+num);
                maps[dy][dx]= 0;
                if((dx==x-1&&dy==y-1)&&min>num)
                    min=++num;
                queue.add(new int[] {dy,dx,++num});
                //visited[dy][dx]= false; 
            }       
        } 
        
       
            if(maps[y-1][x-1]==1)
                return -1;
            
        
        //System.out.println(num);
        return min;
    }
}

결과