Daily LeetCode Challenge - 1091. Shortest Path in Binary Matrix

Problem From.

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

오늘 문제는 왼쪽 끝에서 오른쪽 끝으로 0만 거쳐서 가는 경로중에 가장 짧은 경로를 반환하고 가지 못하면 -1 을 반환하는 문제였다.

이 문제는 BFS 를 통해서 풀 수 있었는데, 각각의 칸마다 4방향을 모두 보면서 0인 칸만 밟으면서 가다가 오른쪽 맨 아래에 도달하면 정답을 반환해주면 되었다.

import java.util.*

class Solution {
    fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        val dx = intArrayOf(1, 1, 0, -1, -1, -1, 0, 1)
        val dy = intArrayOf(0, 1, 1, 1, 0, -1, -1, -1)
        val n = grid.size
        var length = 1
        val q : Queue<IntArray> = LinkedList()

        if (grid[0][0] == 0) {
            q.offer(intArrayOf(0, 0))
            grid[0][0] = 1
        }

        while (!q.isEmpty()) {
            val size = q.size

            for (i in 0..size - 1) {
                val cell = q.poll()

                if (cell[0] == n - 1 &&
                    cell[1] == n - 1) return length

                for (i in 0..7) {
                    val x = cell[0] + dx[i]
                    val y = cell[1] + dy[i]

                    if (x >= 0 && x < n && y >= 0 && y < n &&
                        grid[x][y] == 0) {
                        q.offer(intArrayOf(x, y))
                        grid[x][y] = 1
                    }
                }
            }

            length++
        }

        return -1
    }
}