[LeetCode- Part. 4] 5. 이진 매트릭스 최단경로 (+BFS)

https://leetcode.com/problems/shortest-path-in-binary-matrix/

Shortest Path in Binary Matrix - LeetCode

 

 

 

 

1. 예외처리

(1) 갈 수 없는 경우

(2) 시작점 또는 도착점이 1인 경우

(3) 시작점이 도착점인 경우

2. BFS를 돌면서 도착점이면 리턴

 

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n=grid.length;
        if(grid[0][0]==1 || grid[n-1][n-1]==1) return -1;
        
        int[] start = {0,0,1};
        boolean[][] check= new boolean[n][n];
        check[start[0]] [start[1]]=true;
        if(start[0]==n-1 && start[1]==n-1) return start[2];
        
        int[][] dirs ={{0,1},{1,0},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
        
        Queue<int[]> q= new LinkedList<>();
        q.offer(start);
        while(!q.isEmpty()){
            int[] tmp = q.poll(); 
            for(int[] dir : dirs){
                int x=tmp[0]+dir[0];
                int y=tmp[1]+dir[1];
                int value=tmp[2]+1;
                int[] np={x,y,value};
                if(x==n-1 && y==n-1) return np[2];
                if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==0&&!check[x][y]){
                    check[x][y]=true;
                    q.offer(np);
                }
            }
        }
        return -1;
    }
}

 

+) 세련된 풀이

1. 큐에 넣고, 큐 사이즈만큼 돌면서 체크한다.

2. while문 마지막에 count++;

3. while문에서 return하지 않으면 모두 -1로 예외처리 수행

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n=grid.length;
        if(grid[0][0]==1 || grid[n-1][n-1]==1) return -1;
        
        int[] start = {0,0};
        int count=0;
        boolean[][] check= new boolean[n][n];
        check[start[0]] [start[1]]=true;
        
        int[][] dirs ={{0,1},{1,0},{-1,0},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
        
        Queue<int[]> q= new LinkedList<>();
        q.offer(start);
        while(!q.isEmpty()){
                    //큐의 사이즈만큼 반복한다.
                    int size = q.size();
                    for(int i=0; i<size;i++){
                        int[] tmp = q.poll();
                        if(tmp[0]==n-1 && tmp[1]==n-1) return count+1;
                        for(int[] dir : dirs){
                            int x=tmp[0]+dir[0];
                            int y=tmp[1]+dir[1];
                            int[] np={x,y};
                            if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==0&&!check[x][y]){
                                check[x][y]=true;
                                q.offer(np);
                            }
                    }

                }
               count++;
        }
        return -1;
    
}
}

 

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        //1.ds
        int n=grid.length;
        boolean [][] check = new boolean[n][n];
        int[][] dirs = {{0,1},{1,0},{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
        
        //시작점이나 도착점이 1일 때 예외처리
        if(grid[0][0]==1 || grid[n-1][n-1]==1) return -1;
        
        //초기값 설정
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        check[0][0]=true;
        int count=0;
        
        //2. loop 
        while(!q.isEmpty()){
            int size= q.size();
            for(int i=0;i<size;i++){
                int[] cur = q.poll();
                if(cur[0]==n-1 && cur[1]==n-1) return count+1;
                
                for(int[] dir : dirs){
                    int x = cur[0]+dir[0];
                    int y=cur[1]+dir[1];
                    if(x>=0 && y>=0 && x<n&& y<n &&grid[x][y]==0 && !check[x][y]){
                        check[x][y]=true;
                        q.offer(new int[]{x,y});
                    }
                }
            }
            count++;
        }
        return -1;
    }
}