[코테 적용] [2번 문제] 최단거리(BFS)

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

• Graph 활용 [입문편]

1. Graph 구현
2. DFS 깊이 우선 탐색
3. BFS 너비 우선 탐색

문제

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

BFS의 시간복잡도 O(V), V=n^2, vertax의 개수

접근방법

대놓고 자료구조
2차원 -> 암시적 그래프 표현

다른 예시)

생각의 확장

BFS (최단경로 찾기, 미로찾기 문제) - 출발지부터 가까운 곳부터 탐색하는 특성 - 최단거리 확신

DFS - 모든 경우의 수 비교가 필요해서 최단경로 문제에는 맞지않다.

• 대각선 버전
  
  

코드 구현

from collections import deque

def shortestPathBinaryMatrix(grid):
    shortest_path_len = -1
    row = len(grid)
    col = len(grid[0])
    
    if grid[0][0] != 0 or grid[row-1][col-1] != 0:
        return shortest_path_len
    
    visited = [
        [False] * col
        for _ in range(row)
    ]
    queue = deque()
    queue.append((0, 0, 1))
    visited[0][0] = True # 예약하자마자 방문
    
    delta = [(1, 0), (-1, 0), (0, 1), (0, -1),
             (1, 1), (1, -1), (-1, 1), (-1, -1)]
    
    while queue:
        cur_r, cur_c, cur_len = queue.popleft() # popleft하면 방문했다는 뜻
        # 목적지 도착했을 때 그때 cur_len을 shortest_path_len에 저장
        if cur_r == row - 1 and cur_c == col - 1:
            shortest_path_len = cur_len
            break
        
        # 연결 vertax 확인
        for dr, dc in delta:
            next_r = cur_r + dr
            next_c = cur_c + dc
            if next_r >= 0 and next_r < row and next_c >= 0 and next_c < col:
                if grid[next_r][next_c] == 0 and not visited[next_r][next_c]:
                    queue.append((next_r, next_c, cur_len + 1))
                    visited[next_r][next_c] = True
    
    return shortest_path_len

grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]
print(shortestPathBinaryMatrix(grid))