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

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

프로그래머스

 

 

정답코드

def solution(maps):
    from collections import deque
    q = deque()
    q.append((0, 0)) 
    answer = 0
    chk = [[False] * len(maps[0]) for _ in range(len(maps))]
    dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
    
    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny, nx = ey + dy[i], ex + dx[i]
            if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
                if chk[ny][nx] == False and maps[ny][nx] == 1:
                    chk[ny][nx] = True
                    maps[ny][nx] = maps[ey][ex] + 1
                    q.append((ny, nx))
    
    answer = maps[-1][-1]
    return -1 if maps[-1][-1] == 1 else maps[-1][-1]

나름 쉬운 문제였다.

BFS로 해결하였고, 이동할때마다 +1을 하여서 maps의 끝에 위치하는 값을 최단 거리로 상정하여 출력하였다.