Shortest Path In Binary Matrix
문제 Link
https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ (opens in a new tab)
문제 풀이
반쯤 맞췄다. 강사님의 설명을 듣다가 풀었는데 기본적으로 강사님이 설명해주신 방법과 비슷한 방식으로 코드가 진행이 되었다.
내가 간과한 점은 어떻게 length를 구할 것인가 였는데, 항상 등장하는 패턴이지만 tuple의 값에 꼭 index만 넣으라는 법은 없다는 것이다.
tuple에 row, column 외 length 등의 값을 넣어서 활용할 수 있다는 것이다.
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
if grid[0][0] == 1 or grid[-1][-1] == 1 :
return -1
if len(grid) - 1 == 0 :
return 1
ori_r = len(grid)
ori_c = len(grid[0])
tar_r = len(grid) - 1
tar_c = len(grid[0]) - 1
visited = [[False for _ in range(ori_c)] for _ in range(ori_r)]
ans = -1
q = deque()
q.append((0,0,1))
visited[0][0] = True
while q : # type: tuple
dx = [-1,1,0,0,-1,1,-1,1]
dy = [0,0,-1,1,-1,1,1,-1]
cur_r, cur_c, cur_l = q.popleft()
if cur_c == tar_c and cur_r == tar_r :
return cur_l
for i in range(len(dx)) :
next_r = cur_r + dx[i]
next_c = cur_c + dy[i]
next_l = cur_l + 1
# 길이 확인
if -1 < next_r < ori_r and -1 < next_c < ori_c :
if not visited[next_r][next_c] and grid[next_r][next_c] == 0 :
q.append((next_r, next_c,next_l))
visited[next_r][next_c] = True
return -1 풀이 2
visited를 사용하지 않고 grid를 활용해서 visited를 표현할 수 있다.
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
if grid[0][0] == 1 or grid[-1][-1] == 1 :
return -1
if len(grid) - 1 == 0 :
return 1
ori_r = len(grid)
ori_c = len(grid[0])
tar_r = len(grid) - 1
tar_c = len(grid[0]) - 1
ans = -1
q = deque()
q.append((0,0,1))
while q : # type: tuple
dx = [-1,1,0,0,-1,1,-1,1]
dy = [0,0,-1,1,-1,1,1,-1]
cur_r, cur_c, cur_l = q.popleft()
if cur_c == tar_c and cur_r == tar_r :
return cur_l
for i in range(len(dx)) :
next_r = cur_r + dx[i]
next_c = cur_c + dy[i]
next_l = cur_l + 1
# 길이 확인
if -1 < next_r < ori_r and -1 < next_c < ori_c :
if grid[next_r][next_c] == 0 :
q.append((next_r, next_c,next_l))
grid[next_r][next_c] = 1
return -1