[LeetCode] 1091. Shortest Path in Binary Matrix

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

Algorithm

예외 경우(시작점이나 끝점이 벽인경우)를 놓쳐서 어디가틀린지 해맨 문제다. 항상 문제를 볼때 조건을 꼼꼼히 보고 예외 케이스를 생각하자.

Python

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid)
        if grid[0][0] == 1 or grid[N-1][N-1] == 1:  # 시작점 또는 끝점이 벽인 경우
            return -1
        q = deque([(0, 0, 1)])
        visit = set((0,0))
        direct = [[0, 1], [1, 0], [0, -1], [-1, 0],
                  [1, 1], [-1, -1], [1, -1], [-1, 1]]
        while q:
            i, j, length = q.popleft()
            if i == N - 1 and j == N - 1:
                return length
            for dr,dj in direct:
                ni, nj = i + dr, j + dj
                if 0<=ni<N and 0<=nj<N and grid[ni][nj] == 0 and (ni, nj) not in visit:
                    q.append((ni,nj,length+1))
                    visit.add((ni,nj))
        return -1

Java

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        Queue<Integer[]> q = new LinkedList<>();
        q.add(new Integer[]{0,0,1});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

        int[][] direct =  {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
        
        while (!q.isEmpty()) {
            Integer[] curr = q.poll();
            int i = curr[0];
            int j = curr[1];
            int length = curr[2];

            if (i==n-1 && j==n-1) return length;

            for(int[] d: direct){
                int ni = i + d[0];
                int nj = j + d[1];
                if(Math.min(ni,nj) >= 0 && Math.max(ni,nj) < n &&
                grid[ni][nj] == 0 && !visited[ni][nj]) {
                    q.add(new Integer[]{ni, nj, length + 1});
                    visited[ni][nj] = true;
                }
            }
        }
        return -1;
    }
}