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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

설계

- BFS 문제

 

def solution(maps):
    N = len(maps)
    M = len(maps[0])

    q = [(0, 0, 1)]
    visit = [[0] * M for _ in range(N)]     # N, M 헷갈림 주의
    visit[0][0] = 1
    answer = -1

    while q:
        x, y, cnt = q.pop(0)
        if x == (N-1) and y == (M-1):       # 최종 목적지 index는 -1씩
            answer = cnt
            break

        for i in range(4):
            dx = [-1, 0, 1, 0]
            dy = [0, 1, 0, -1]
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visit[nx][ny] == 0:
                    if maps[nx][ny] == 1:
                        visit[nx][ny] = 1
                        q.append((nx, ny, cnt + 1))
    return answer