[leetcode] 1293. Shortest Path in a Grid with Obstacles Elimination

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

---

m x n 정수 2차원 배열이 주어진다. 각 셸은 0(비어있음) 혹은 1(장애물) 이다. 최대 k개의 장애물을 제거할 수 있다고 할 때, (0, 0) -> (m-1, n-1)로 이동할 수 있는 최소 걸음 수를 구하라. 배열에서 1칸 이동을 1 걸음수로 본다. 상하좌우로 한 칸씩 이동할 수 있다.

불가능한 경우 -1을 반환하라.

---

BFS로 풀었다.

탐색했는지 여부를 저장하기 위해 visits[x][y][k] 배열을 하나 만든다.

visits[x][y][k] = 장애물 제거가능 횟수가 k번 남았을 때, grid[x][y]를 탐색한 적이 있는지 여부.

 

BFS로 (0,0) 위치에서 상하좌우로 이동시키면서 탐색한다.

만일 이동하고자 하는 좌표(let, (nx, ny))의 visits 값이 true인 경우 탐색을 중지한다.

grid[nx][ny]가 장애물이 아닌 경우 k는 그대로 유지, 걸음수만 +1 해준다.

grid[nx][ny]가 장애물인 경우 k가 0이면 더 이상 탐색이 불가능하므로 탐색을 중지한다.

k가 1이상이면 장애물을 한 번 제거했으므로 -1 해주고 걸음수는 +1 해서 탐색을 이어나간다.

 

BFS이기 때문에 가장 먼저 (m-1, n-1)에 도달했을 때의 걸음수가 정답이된다.

만일 (m-1, n-1)에 도달하지 못하고 모든 방향의 탐색들이 불가능하여 중지된 경우 불가능한 경우이므로 -1을 반환한다.

 

시간/공간 복잡도는 O(nmk).

---

소스코드 : https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/