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

BFS 기본적인 문제 다시 한번 더 연습.!

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

 

알고리즘

간단한BFS  문제이다. 시작점 (0, 0)에서 시작하여 한 칸씩 직접 탐사하되,
(N, M)에 닿았을 경우 (닿지 않았을 수 있으므로) 닿았을때의 거리를 별도의 리스트에 저장시킨다.

별도의 리스트가 비어있다면, -1을 return 그렇지 않다면 최솟값을 return 시켜주자.

코드

from collections import deque
def bfs(x, y, maps):
    queue = deque()
    answer_list = set()
    queue.append((0, 0))
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]):
                continue
            elif maps[nx][ny] == 0:
                continue
            elif maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                if nx == len(maps)-1 and ny == len(maps[0])-1:
                    answer_list.add(maps[nx][ny])
                queue.append((nx, ny))          

    return answer_list
def solution(maps):   
    answer = bfs(0, 0, maps)
    if len(answer) == 0:
        return -1
    else:
        return min(answer)

answer_list에 데이터를 넣는 과정에서 set을 활용하여 복잡도상의 이득을 취하였다.