[LeetCode] Shortest Path in Binary Matrix

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

문제 파악

-방향을 탐색하는 문제

-최소 거리를 구하는 BFS문제

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

 

접근 방법

💡 -좌표 (x,y) -큐에서 poll()하여 방향에 따라 더하거나 뺀다.

-8방향은 0,0 기준점을 기준으로 둘러싼 방향

-8방향을 2차원 배열로 미리 선언해두어 for문으로 조회하고 현재 값에 더한다.

1)시작점 혹은 끝점이 0이 아니거나,

2) 끝점까지 가는 명확한 길이 없다면 즉, 큐 순회가 끝날 때까지 끝점에 도달하지 못하고 가는 길이 끊긴다면

⇒ -1 리턴

 

코드 구현

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n=grid.length;
        //8방
        int[][] arrow={
            {-1,-1},{-1,0},{-1,1},
            {0,-1},{0,1},
            {1,-1},{1,0},{1,1}
        };
        //최소 거리 = BFS
        if(grid[0][0]!=0 || grid[n-1][n-1]!=0) return -1;
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{0,0,1});//x,y,length

        while(!que.isEmpty()){
            int[] node=que.poll();
            int x=node[0];int y=node[1];int length=node[2];
            if(x==n-1 && y==n-1){
                return length;
            }
            grid[x][y] = 1;
            for(int[] to:arrow){
                int toX = x+to[0];
                int toY = y+to[1];
                
                if(toX<n && toX>=0 && toY<n && toY>=0 && grid[toX][toY]==0){
                    que.add(new int[]{toX,toY,length+1});
                    grid[toX][toY]=1;
                }
            }
        }
        return -1;
    }
}

배우게 된 점

-들어가서 방향 돌기

-조건에 안걸리면 순회를 이어나간다. (그래프의 경우 0 이상이고 벽에 안부딫히고-최댓값보다 작고..) 등등

-visited 체크