[LeetCode] 1091. Shortest Path in Binary Matrix (해석, Kotlin 풀이)

문제

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

주어진 n x n 이진행렬인 grid에서, 배열의 가장 짧은 Clear Path의 길이를 구하여라. 만약 Clear Path가 없다면, -1을 반환하여라.

 

이진행렬에서의 Clear Path는 다음 조건을 만족하는 (0, 0) 좌표에서 (n-1, n-1) 좌표까지의 경로 이다.

조건

- 방문하는 모든 좌표의 값은 0이다.

- 경로에서 모든 인접한 좌표는 8방향(상, 하, 좌, 우, 우상, 우하, 좌상, 좌하)으로 연결되어있다. 

 

Clear Path의 길이는 경로 내 방문한 좌표의 수 이다. 

풀이

전형적인 최단 거리를 구하는 BFS 문제 : Queue 자료구조를 사용하여 너비 우선 탐색을 진행하고, 목표에 도달하면 STOP!

class LT_1091_ShortestPathInBinaryMatrix {
    val di = listOf(-1, -1, -1, 0, 0, 1, 1, 1)
    val dj = listOf(-1, 0, 1, -1, 1, -1, 0, 1)

    fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
        var result = -1
        val n = grid.size

        if(grid[0][0] != 0) return result

        val visited = Array(n) { BooleanArray(n) { false } }
        val q = ArrayDeque<List<Int>>()
        visited[0][0] = true
        q.add(listOf(0, 0, 1))

        while (q.size > 0) {
            val cur = q.poll()
            if(cur[0] == n-1 && cur[1] == n-1) {
                result = cur[2]
                break
            }

            for(i in 0..7) {
                val ni = cur[0] + di[i]
                val nj = cur[1] + dj[i]

                if(ni in 0 until n && nj in 0 until n) {
                    if(grid[ni][nj] == 0 && !visited[ni][nj]) {
                        q.add(listOf(ni, nj, cur[2] + 1))
                        visited[ni][nj] = true
                    }
                }
            }
        }
        return result
    }
}

https://github.com/jeongum/algorithm/blob/master/LT_1091_ShortestPathInBinaryMatrix.kt

GitHub - jeongum/algorithm

결과

시간 복잡도&공간 복잡도 모두 만족 ! :)