[LeetCode] 1091. Shortest Path in Binary Matrix

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

LeetCode - The World's Leading Online Programming Learning Platform

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
- All the visited cells of the path are 0.
- All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
- The length of a clear path is the number of visited cells of this path.

 

n x n 이진 행렬 grid가 주어졌을 때, 행렬 내에서 가장 짧은 명확한 경로의 길이를 반환하세요. 명확한 경로가 없으면 -1을 반환하세요. 이진 행렬에서의 명확한 경로는 다음 조건을 만족하는 상단 왼쪽 셀(즉, (0, 0))에서 하단 오른쪽 셀(즉, (n - 1, n - 1))까지의 경로를 의미합니다:

- 경로상의 모든 방문 셀은 0입니다.

- 경로의 모든 인접 셀은 8방향으로 연결되어 있습니다(즉, 서로 다르며 한 변이나 모서리를 공유합니다).

- 명확한 경로의 길이는 이 경로의 방문 셀 수입니다.

---

접근 방법

1. 문제 이해
방문 가능한 셀은 ‘0’이고 8방향으로 이동 가능합니다. 
좌측상단에서 우측하단까지 가장 짧게 이동할 수 있는 길을 찾습니다. (없을 시 -1 리턴)
따라서 만약 좌측상단이 또는 우측하단이 1이면 바로 -1을 리턴합니다.
리턴할 값은 int로 방문한 셀의 수입니다.

 

2. 어떤 알고리즘을 써야 할까
grid를 전체 탐색해야 하므로 완전탐색 - 그중에서 가장 빠른 길을 가야 하므로 BFS를 선택했습니다.

 

3. 코드 설계
BFS를 사용할 것이므로 예약용으로 사용할 Queue 선언합니다.
    - BFS와 Queue는 짝꿍!
방문했는지 확인하기 위해 visited[][]를 선언합니다.
8방향으로 이동할 수 있는 dr, dc를 선언합니다.

static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};

 

bfs(0,0)부터 시작해서 8방향으로 이동하면서 bfs(n-1, n-1)까지 이동합니다.
방문표시를 찍은 셀의 개수를 반환합니다.

 

코드 구현

1. 실패 코드

class Solution {
    static boolean[][] visited;
    static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};
    static int rowLength;
    static int colLength;

    // 셀이 유효한지 체크
    public static boolean isValid(int r, int c, int[][] grid) {
        return (r >= 0 && r < rowLength) && (c >= 0 && c < colLength) && (grid[r][c] == 0);
    }

    public static int shortestPathBinaryMatrix(int[][] grid) {
        int cnt = 0;
        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];

        // grid를 돌면서 유효한 셀을 bfs에 넘기기
        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (grid[0][0] == 1) return -1;
                if (grid[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j, grid);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void bfs(int r, int c, int[][] gird) {
        Queue<int[]> queue = new LinkedList<>();
        // 큐에 넣고
        queue.offer(new int[]{r, c});
        // 방문 표시
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            // 큐에 있는 걸 뽑은 게 현재 노드
            int[] cur = queue.poll();
            int curLow = cur[0];
            int curCol = cur[1];

            // for문을 8방향 돌리면서 nextNode 탐방
            for (int i = 0; i < 8; i++) {
                int nextLow = curLow + dr[i];
                int nextCol = curCol + dc[i];
                // 유효한지, 방문했는지 확인
                if (isValid(nextLow, nextCol, gird)) {
                    if (!visited[nextLow][nextCol]) {
                        // 큐에넣고
                        queue.offer(new int[]{nextLow, nextCol});
                        // 방문표시
                        visited[nextLow][nextCol] = true;
                    }
                }
            }
        }
    }
}

 

Testcase 확인 ➡ 상황 : 테스트케이스의 출력이 전부 1로 나오는 문제

Case 1.
Input : grid = [[0,1],[1,0]]
Output : 1
Expected : 2

Case 2.
Input : grid = [[0,0,0],[1,1,0],[1,1,0]]
Output : 1
Expected : 4

 

원인 :

1. grid[n-1][n-1] == 1 일 경우에도 -1을 리턴해야 합니다.

• 해당 부분이 for 루프 내에 있는데, 루프 시작 전에 한 번만 수행해야 합니다. 매번 체크하는 것은 비효율적입니다.

2. 경로 길이를 저장하는 변수가 없습니다. → 출력해야 할 부분인데!!! 꼭 챙겨야 한다!!

• 경로 길이를 queue에 같이 저장합니다.
• (n-1, n-1) 위치에 도달했을 때의 경로 길이를 반환해야 합니다.

3. 불필요한 이중 for문 제거

• 이유: 해당 for 루프는 모든 그리드 셀을 순회하며 각 셀을 시작점으로 BFS를 수행하고 있습니다. 그러나 이 문제에서는 모든 셀을 시작점으로 할 필요가 없으며, 오직 (0, 0)만을 시작점으로 하여 (n-1, n-1)까지의 경로를 찾으면 됩니다.
• 해당 for 루프는 제거하고 BFS를 단 한 번만, (0, 0)에서 시작하여 수행합니다.

public static int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];

        // 수정 필요한 부분
        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (grid[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j, grid);
                }
            }
        }
    }

 

2. 성공 코드

import java.util.*;

class Solution {
    static boolean[][] visited;
    static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};
    static int rowLength;
    static int colLength;

    public static boolean isValid(int r, int c, int[][] grid) {
        return (r >= 0 && r < rowLength) && (c >= 0 && c < colLength) && (grid[r][c] == 0);
    }

    public static int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];

        return bfs(0,0,grid);

    }

    public static int bfs(int r, int c, int[][] grid) {
        int n = grid.length;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c, 1});
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curLow = cur[0];
            int curCol = cur[1];
            int curLength = cur[2];

            if (curLow == n-1 && curCol == n-1) return curLength;

            for (int i = 0; i < 8; i++) {
                int nextLow = curLow + dr[i];
                int nextCol = curCol + dc[i];

                if (isValid(nextLow, nextCol, grid)) {
                    if (!visited[nextLow][nextCol]) {
                        queue.offer(new int[]{nextLow, nextCol, curLength+1});
                        visited[nextLow][nextCol] = true;
                    }
                }
            }
        }
        return -1;
    }
}

 

배우게 된 점

문제가 길고 코드가 길어서 길을 잃더라도 그래서 무엇을 리턴해야 할지 항상 유념하기!