[프로그래머스][python][BFS] 게임 맵 최단거리 문제

프로그래머스

✏️ 내가 작성한 코드 - BFS

from collections import deque

def solution(maps):

    q = deque()
    q.append([0,0])

    n = len(maps) # 행
    m = len(maps[0]) # 열

    move = [[1,0],[-1,0],[0,-1],[0,1]] # 움직임(상,하,좌,우)
    visit = [[-1]*m for _ in range(n)] # 방문 배열 (visit에 해당 행,열까지의 거리 저장함.)
    visit[0][0] = 1 # 거리구할때 0행0열도 포함해서 구하므로 1부터시작.

    while q:
        dn, dm = q.popleft() # 이동 시작할 행,열

        for i in range(4): # 상,하,좌,우로 4가지 방향으로 이동 가능
            next_dn = dn + move[i][0]
            next_dm = dm + move[i][1]

            if next_dn >= n or next_dn < 0 or next_dm >= m or next_dm < 0: # 지도 범위 벗어나면
                continue
            if maps[next_dn][next_dm] == 1 and visit[next_dn][next_dm] == -1: # 지도에서 벽이아님(1) and 방문한적없음(visit[행][열]=-1)
                visit[next_dn][next_dm] = visit[dn][dm] + 1 # 해당 행열까지의 거리수로 update
                q.append([next_dn,next_dm])
    return visit[n-1][m-1]

✏️ 참고

visit에 방문했냐/안했냐(True/False)를 넣는 게 아니라 해당 [행][열]까지의 거리를 계산해서 넣고

마지막 위치인 [n-1][m-1]을 출력해주면서 최단 거리를 구하면된다.