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

from collections import deque

def solution(maps):

    visited = [[0] * len(maps[0]) for _ in range(len(maps))]
    visited[0][0] = 1
    q = deque()
    q.append((0, 0))
    while q:
        cy, cx = q.popleft()
        for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
                if visited[ny][nx] == 0 and maps[ny][nx] == 1:
                    if ny == len(maps)-1 and nx == len(maps[0]) -1:
                        visited[ny][nx] += visited[cy][cx] + 1
                        print(visited)
                        return visited[ny][nx]
                    q.append((ny, nx))
                    visited[ny][nx] += visited[cy][cx] + 1

    return -1

bfs를 활용한 풀이. 방문배열을 캐릭터가 이동 한 칸의 개수로 놓고 방문 할 때 마다 그 전 방문의 개수 + 1을 해준다.

만약 목표지점에 도착 한다면 그 지점의 값을 return 해주고 목표지점을 찾지 못하고 bfs가 끝나게 되면 -1을 return 해준다.