프로그래머스. 게임 맵 최단거리 파이썬 풀이

프로그래머스. 찾아라 프로그래밍 마에스터. Level 2. 게임 맵 최단거리 파이썬 풀이

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/1844

전형적인 BFS 문제

from collections import deque   

def solution(maps):
    # 순서대로 상하좌우
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    w = len(maps[0]) # 가로 길이
    h = len(maps) # 세로 길이
    
    visited = [[-1]*w for _ in range(h)]  # 거리, 방문테이블 초기화
    q = deque()
    q.append([0,0])  # 시작 지점 큐에 추가
    visited[0][0] = 1 # 시작 지점은 1
    
    while q:
        y, x = q.popleft()
        
        # 네 가지 방향 모두 고려
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w: # 범위를 벗어나지 않는다면
                if maps[ny][nx] == 1: # 길이라면
                    if visited[ny][nx] == -1: # 방문하지 않았다면
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        
    answer = visited[-1][-1]
    
    return answer