[Python] 프로그래머스(Lv2) - 게임 맵 최단거리

안녕하세요 !

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

프로그래머스 게임 맵 최단거리 문제입니다.

답이 되는 최단거리

풀이

최단거리를 구하는 문제로 BFS로 풀 수 있습니다.

먼저, maps 배열을 0으로 둘러싸줍니다. while q 안에서 배열 밖을 벗어났는지 체크하는 걸 안하기 위해서 0으로 둘러싸줬습니다.

check 배열을 만들어 0으로 초기화 합니다. 0이라면 아직 지나지 않은 위치가 됩니다.
q로 너비탐색을 하면서 현재좌표가 (n, m) 이라면 return 해줍니다.

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def solution(maps):
    q = deque()

    n = len(maps)
    m = len(maps[0])
    maps = [[0] + r + [0] for r in maps]
    maps = [[0] * (m + 2)] + maps
    maps += [[0] * (m + 2)]

    q.append([1, 1])
    check = [[0] * len(maps[0]) for _ in range(len(maps))]
    check[1][1] = 1
       
    while q:
        x, y = q.popleft()
        if x == n and y == m:
            return check[n][m]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if check[nx][ny] == 0 and maps[nx][ny] == 1:
                q.append([nx, ny])
                check[nx][ny] = check[x][y] + 1
        
    return -1