[LeetCode] 1091. Shortest Path in Binary Matrix - Java

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

Shortest Path in Binary Matrix - LeetCode

---

문제

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.

 

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

 

Constraints:

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

---

풀이

풀이 과정

길이가 n이고 값이 0과 1로 이루어진 정사각형 모양의 2차원배열 grid가 주어지고 0은 이동을 했던 지점, 1은 이동을 하지 않았던 지점을 나타낸다.

왼쪽 상단에서 출발하여 오른쪽 하단에 도착하려고 할 때 최단 거리를 구하는 문제이다.

이동은 대각선을 포함한 8방향 모두 이동이 가능하고 출발점에서 도착점으로 가는 최단 경로가 존재하지 않는 경우 -1을 return한다.

 

먼저 최단 경로가 1이거나 구할 수 없는 경우를 먼저 제외한다.
배열의 길이를 n이라고 할 때 출발점의 값이 0이고 배열의 길이 n이 1인 경우는 항상 그 자체로 최단거리이므로 바로 1을 return 한다.
만약 출발점이나 도착점의 값이 0이 아닌 경우는 출발점에서 도착점으로 이어지는 경로를 구할 수 없으므로 -1을 return한다.

// 배열의 길이
int n = grid.length;

// 배열이 한 칸이고 이동가능한 경우 최단거리 1을 return
if(grid[0][0] == 0 && n == 1) return 1;
// 출발점이나 도착점이 이동 불가능한 지점인 경우 경로탐색이 불가능 하므로 -1을 return
if(grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;

 

이외의 경우에는 큐를 이용한 BFS탐색을 이용하기로 한다.
우선 현재 좌표를 기준으로 왼쪽 위, 중앙 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 중앙 아래, 오른쪽 아래 순서대로 탐색할 방향을 지정한다.

// 탐색할 방향 (왼쪽 위, 중앙 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 중앙 아래, 오른쪽 아래)
int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

 

다음으로 탐색에 사용할 큐를 선언해주고 출발점인 (0,0) 좌표를 삽입한다.

// 탐색에 사용할 큐 선언
Queue<int[]> q = new LinkedList<>();
// 큐에 출발점 삽입
q.offer(new int[] {0, 0});

 

너비우선탐색을 위해서는 특정 지점의 방문 여부를 알 필요가 있는데 방문한 지점의 값을 -1로 바꾸어 방문 여부를 표시해준다.

// 출발점값을 -1로 방문여부 표시
grid[0][0] = -1;

 

정답 카운트를 0부터 시작하여 큐가 빌 때까지 반복하여 탐색을 한다.
먼저 정답 카운트를 하나 증가 시키고 현재 큐에 있는 모든 값을 반복 하여 탐색한다.
현재 탐색중인 지점이 도착점인 경우 정답값을 return 해준다.

그렇지 않은 경우에는 나머지 8방향 탐색을 계속한다.
처음에 선언해준 탐색 방향대로 새로운 행 좌표와 열 좌표를 각각 구하고

1. 새로운 좌표가 배열을 벗어나는 경우
2. 방문 가능한 좌표가 아닌 경우( 값이 1인 경우 )
3. 이미 방문한 경우 ( 값이 -1인 경우 )

이러한 경우에는 탐색에서 제외한다.
탐색이 가능한 경우에는 새로운 좌표의 값을 -1로 변경하여 방문 표시를 하고, 큐에 새로운 좌표값을 추가한다.

// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
    // 정답 카운트 증가
    answer++;
    // 현재 큐에 있는 모든 요소 탐색
    for(int i = q.size(); i > 0; i--) {
        // 현재 탐색중인 지점
        int[] point = q.poll();
        // 현재 탐색중인 지점의 행 좌표
        int row = point[0];
        // 현재 탐색중인 지점의 열 좌표
        int col = point[1];

        // 도착점에 도착한 경우 정답 카운트를 return
        if(row == n - 1 && col == n - 1) return answer;

        // 8방향 탐색
        for(int[] dir : dirs) {
            // 새로운 행 좌표
            int newRow = row + dir[0];
            // 새로운 열 좌표
            int newCol = col + dir[1];
            // 새로운 좌표가 배열을 벗어나는 경우 탐색 제외
            if(newRow < 0 || newRow == n || newCol < 0 || newCol == n) continue;
            // 새로운 좌표가 방문 가능한 좌표가 아니거나 이미 방문한 경우 탐색 제외
            if(grid[newRow][newCol] != 0) continue;

            // 현재 좌표 -1로 방문 표시
            grid[newRow][newCol] = -1;
            // 큐에 새로운 좌표값 주가
            q.offer(new int[] {newRow, newCol});
        }
    }
}

---

최종 코드

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        // 배열의 길이
        int n = grid.length;
        
        // 배열이 한 칸이고 이동가능한 경우 최단거리 1을 return
        if(grid[0][0] == 0 && n == 1) return 1;
        // 출발점이나 도착점이 이동 불가능한 지점인 경우 경로탐색이 불가능 하므로 -1을 return
        if(grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
        
        // 탐색할 방향 (왼쪽 위, 중앙 위, 오른쪽 위, 왼쪽, 오른쪽, 왼쪽 아래, 중앙 아래, 오른쪽 아래)
        int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        // 탐색에 사용할 큐 선언
        Queue<int[]> q = new LinkedList<>();
        // 큐에 출발점 삽입
        q.offer(new int[] {0, 0});
        // 출발점값을 -1로 방문여부 표시
        grid[0][0] = -1;
        
        // 정답 카운트
        int answer = 0;
        
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 정답 카운트 증가
            answer++;
            // 현재 큐에 있는 모든 요소 탐색
            for(int i = q.size(); i > 0; i--) {
                // 현재 탐색중인 지점
                int[] point = q.poll();
                // 현재 탐색중인 지점의 행 좌표
                int row = point[0];
                // 현재 탐색중인 지점의 열 좌표
                int col = point[1];
                
                // 도착점에 도착한 경우 정답 카운트를 return
                if(row == n - 1 && col == n - 1) return answer;
                
                // 8방향 탐색
                for(int[] dir : dirs) {
                    // 새로운 행 좌표
                    int newRow = row + dir[0];
                    // 새로운 열 좌표
                    int newCol = col + dir[1];
                    // 새로운 좌표가 배열을 벗어나는 경우 탐색 제외
                    if(newRow < 0 || newRow == n || newCol < 0 || newCol == n) continue;
                    // 새로운 좌표가 방문 가능한 좌표가 아니거나 이미 방문한 경우 탐색 제외
                    if(grid[newRow][newCol] != 0) continue;
                    
                    // 현재 좌표 -1로 방문 표시
                    grid[newRow][newCol] = -1;
                    // 큐에 새로운 좌표값 주가
                    q.offer(new int[] {newRow, newCol});
                }
            }
        }

        return -1;
    }
}

---