Daily LeetCode Challenge - 1293. Shortest Path in a Grid with Obstacles Elimination

Problem From.
https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

이 문제는 k 와 함께 0 과 1 로 이루어진 matrix 가 주어진다.

matrix 에서 1 은 장애물을 뜻하며, k 는 그 장애물을 부수고 갈 수 있는 횟수를 뜻한다.

(0,0) 에서 시작하여 오른쪽 맨 아래의 블럭에 도달할때까지 장애물을 부수며 갈 수 있는 최단거리를 구하여야 되었다.

처음에는 DFS 를 통해서 갈 수 있는 모든 경우의 수를 구하려고 하였지만, 그렇게 하면 시간이 너무 오래 걸리기에, BFS 를 통해서 문제를 풀었다.

또 가장 중요한 부분은 각 블럭을 visit 할때, 그때마다 k 값이 달라질 수 있다.

예를 들면, 블럭을 1개 부수고 (1,1) 에 도달하는것과, 블럭을 2개 부수고 (1,1) 에 도달하는 것은 다른 경로로 취급하여야 한다.

그래서 visited 배열을 선언할 때, 안에 BooleanArray 를 k+1 의 크기만큼 선언해주어서, 각 블록에 도달할 때, 몇개의 블록을 부수고 도달하였는지로 구분할 수 있게 하였다.

class Solution {
    
    fun shortestPath(grid: Array<IntArray>, k: Int): Int {
        
        val visited = Array(grid.size) { Array(grid[0].size) { BooleanArray(k + 1) } }
        
        val queue : Queue<Array<Int>> = LinkedList()
        
        val dirs = arrayOf(intArrayOf(0,1),intArrayOf(0,-1),intArrayOf(1,0),intArrayOf(-1,0))
        
        queue.offer(arrayOf(0, 0, k, 0))
        
        while(queue.isNotEmpty()) {
            val list = queue.poll()
            
            val x = list[0]
            val y = list[1]
            val obs = list[2]
            val move = list[3]
            
            if(visited[x][y][obs]) continue
            visited[x][y][obs] = true
            

            if(x == grid.lastIndex && y == grid[0].lastIndex) {
                return move
            }
            
            dirs.forEach { dir ->
                val x = x + dir[0]
                val y = y + dir[1]
                
                if(x < 0 || x >= grid.size || y < 0 || y >= grid[0].size) return@forEach
                
                if(grid[x][y] == 1 && obs > 0) {
                    queue.offer(arrayOf(x, y, obs - 1, move + 1))
                } else if(grid[x][y] == 0) {
                    queue.offer(arrayOf(x, y, obs, move + 1))
                }
            }
   
        }
        
        return -1
        
    }
    
}

위 풀이의 시간복잡도는 O(mnk)

평범한 BFS 문제인줄 알았지만, 각 경로를 부순 블럭의 갯수로 구별해야 하는 문제였다.

난이도 Hard 인 문제는 어렵지만, 그만큼 생각할것도 많고 배울것도 많아서 좋은것 같다.