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

문제

 

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

프로그래머스

 

풀이

전형적인 BFS문제

 

visited의 초기값을 -1로 두고 (0,0)은 1로 두어 세팅. 이후에 한 칸씩 지나가면서 visited값을 1씩 더해주면서 방문표시.

맵을 벗어나지않고, 벽이 아니고, 방문한 적이 없는 경우에 queue에 넣어서 반복.

 

deque을 이용해 popleft()를 이용하여, 리스트의 pop(0)보다 시간을 줄임

from collections import deque
def solution(maps):
    d = [(1,0),(0,1),(-1,0),(0,-1)]
    queue = deque()
    queue.append((0,0))
    n = len(maps)
    m = len(maps[0])
    visited = [[-1 for _ in range(m)] for _ in range(n)]
    visited[0][0] = 1
    while queue:
        cur = queue.popleft()
        if cur == (n - 1,m - 1):
            return visited[cur[0]][cur[1]]
        for i in range(4):
            new = (cur[0] + d[i][0], cur[1] + d[i][1])
            if new[0] < 0 or new[1] < 0 or new[0] >= n or new[1] >= m:
                continue
            if visited[new[0]][new[1]] != -1:
                continue
            if maps[new[0]][new[1]] == 0:
                continue
            queue.append(new)
            visited[new[0]][new[1]] = visited[cur[0]][cur[1]] + 1
    return -1

 

_____________________________________________________________________________________________________

 

쉬운 BFS문제지만 Python이 자꾸 헷갈림.