Shortest Path in Binary Matrix

Shortest Path in Binary Matrix - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

• 격자 원소 갯수 최대 1만개
• 8가지 방향 있으니 최대 연산수 8만
• 완탐가능
• clear path 가 없는 경우 -1 를 return 해야함

아이디어

가장 최단 거리라는 보장?

bfs 를 활용하여 가장 먼저 닿을때까지의 거리를 계산하면 가능

한칸한칸 나갈때마다 cnt 를 1 증가시켜주고 만약 현재칸이 도착지점(n-1,n-1) 이면 현재까지 cnt+1 를 return 해주면 됨.

만약 0,0 이나 n-1,n-1 값이 0이 아니면 clear path 가 처음부터 있을수 없음

시간복잡도

자료구조

코드 구현 [필수 작성]

1차 시도 (20분 소요)

히든테스트케이스 통과 실패

코너케이스가 뭐가 있을지 생각중

[[0]] → 1

아예 grid 가 1칸만 있는 악의적인 케이스 생각을 못함

제한 조건 확인하자!!!

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        visited = [[False]*len(grid[0]) for _ in range(len(grid))]
        
        if grid[0][0] == 1 or grid[len(grid)-1][len(grid)-1] == 1:
            return -1

        def is_valid(r,c):
            nonlocal grid

            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == 0 and visited[r][c] == False:
                return True
            else:
                return False

        def bfs(input_r,input_c,step):
            nonlocal grid

            dr = [0,1,1,1,0,-1,-1,-1]
            dc = [1,1,0,-1,-1,-1,0,1]
            q = deque([(input_r,input_c,step)])

            while q:
                r,c,step = q.popleft()
                for i in range(8):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if is_valid(nr,nc):
                        if nr == len(grid)-1 and nc == len(grid)-1:
                            return step+1
                        q.append((nr,nc, step+1))
                        visited[nr][nc] = True

            return -1

        visited[0][0] = True

        return bfs(0,0,1)

2차 시도

n-1,n-1 인덱스 도착 조건 위치를 바꿔줌으로써 해결

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        visited = [[False]*len(grid[0]) for _ in range(len(grid))]
        
        if grid[0][0] == 1 or grid[len(grid)-1][len(grid)-1] == 1:
            return -1

        def is_valid(r,c):
            nonlocal grid

            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == 0 and visited[r][c] == False:
                return True
            else:
                return False

        def bfs(input_r,input_c,step):
            nonlocal grid

            dr = [0,1,1,1,0,-1,-1,-1]
            dc = [1,1,0,-1,-1,-1,0,1]
            q = deque([(input_r,input_c,step)])

            while q:
                r,c,step = q.popleft()
                if r == len(grid)-1 and c == len(grid)-1:
                    return step
                for i in range(8):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if is_valid(nr,nc):
                        q.append((nr,nc, step+1))
                        visited[nr][nc] = True

            return -1

        visited[0][0] = True

        return bfs(0,0,1)

배우게 된 점 [ 필수 X ]

악의적인 코너케이스 제한조건 확인하자!!!

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!