[프로그래머스 Lv2] 게임 맵 최단거리

최종 코드

from collections import deque

def solution(maps):
    n = len(maps)  # n이 세로
    m = len(maps[0]) # m이 가로
   
    visited = [[-1] * m for _ in range(n)]
    
    queue = deque()
    queue.append((0, 0)) # (x, y) 순서로 삽입
    visited[0][0] = 1   
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while queue:
        # 현재 위치 꺼내기 (x, y 순서)
        x, y = queue.popleft()
        
        # 사방 탐색
        for i in range(4):
            temp_x = x + dx[i]
            temp_y = y + dy[i]
            
            if 0 <= temp_x < m and 0 <= temp_y < n:
                if maps[temp_y][temp_x] != 0 and visited[temp_y][temp_x] == -1:
                    visited[temp_y][temp_x] = visited[y][x] + 1
                    queue.append((temp_x, temp_y)) 
    return visited[n-1][m-1]

처음엔 dfs인가 싶었는데, 가능한 경로 중 최소거리를 찾는 문제였기 때문에 bfs가 적절하다고 판단했다. visited 배열을 map과 같은 크기로 만들어놓고, 방문했을 당시 이동거리를 넣어 이전 값을 추적하기 쉽게 했다.

두 가지를 리마인드 할 수 있었다

• 이동 거리 문제는 이동을 미리 정의해둘 것
• 조건문에서 범위 먼저 검사할 것 -> 범위를 나중에 검사할 경우, 범위를 벗어난 값에 의해 후속 조건은 확인도 못한 채 에러가 날 수 있음