[프로그래머스] Lv.2 게임 맵 최단거리 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844
• BFS(너비 우선 탐색)으로 구현

from collections import deque

def solution(maps):

    #         상,하                 좌,우
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    q = deque([(0, 0)]) # 시작 좌표

    visit = [[0] * len(maps[0]) for _ in range(len(maps))]  # 방문 및 이동횟수 체크 리스트
    visit[0][0] = 1     # 방문 및 이동횟수 체크
    maps[0][0] = 0	# 출발지에서 이동한 후에 다시 출발지로 못 오게 하기 위해 0으로 세팅

    while q:    # q가 빌 때까지 계속
        x, y = q.popleft()                     # 현재 좌표의 위치
        for i in range(4):                     # 상, 하, 좌, 우를 반복
            nx, ny = x + dx[i], y + dy[i]      # 다음 이동할 좌표 nx = 상, 하 ny = 좌, 우
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):  # 맵을 이탈하지 않았을 때
                if maps[nx][ny] == 1 and not visit[nx][ny]: # 이동할 곳이 1이고 방문하지 않았을 때
                    visit[nx][ny] = visit[x][y] + 1             # visit에 이동 횟수를 저장
                    q.append((nx, ny))                          # 현재 좌표를 저장

    if visit[-1][-1]:   # visit의 제일 마지막 요소(이동 횟수)가 있으면 리턴 (도착점에 도달할 수 있을 때)
        return visit[-1][-1]
        
    return -1