[프로그래머스/Python] - Lv3 / 게임 맵 최단거리

level3 - BFS - 게임 맵 최단거리\

from collections import deque
def solution(maps):
    g = maps
    n = len(maps) #세로
    m = len(maps[0]) #가로
    dis = [[0] * m for _ in range(n)]
    dis[0][0] = 1#시작점 1
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    #0은 벽 1은 이동 가능
    def BFS(a,b):
        dq = deque()
        dq.append((a,b))
        g[a][b] = 0 #방문 처리
        
        while dq:
            x,y = dq.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<n and 0<=ny<m: #경계선
                    if g[nx][ny] == 1: #방문 전
                        g[nx][ny] = 0
                        dis[nx][ny] = dis[x][y] + 1
                        dq.append((nx,ny))
    
    BFS(0,0)
    
    if dis[n-1][m-1] == 0: #갈 수 없음
        return -1
    else:
        return dis[n-1][m-1]

코멘트

해당 문제는 전형적인 BFS 최단거리 문제였다. 있는 그대로 시작점을 기준으로 동서남북 계속 탐색하면서 방문하지 않은 지점이 있다면 큐에 넣은 이후에 방문처리 이후. 최단거리 dis 리스트에 기록하고 도착점 확인!