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

문제

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

 

풀이

그래프 형식의 문제이니만큼 그래프 탐색을 이용했고, BFS로 풀었습니다. 

 

우선 BFS에 필요한 큐를 구현하기 위해서 collections 라이브러리의 deque 자료구조를 사용했습니다.

 

일반 리스트로도 pop(0) 메소드를 통해 큐의 역할을 구현할 수는 있지만 이 경우 맨 앞의 원소를 제거할 때는 O(n) 시간이 걸린다는 단점이 있어서 deque() 라이브러리를 사용했습니다. 

 

from collections import deque

def solution(maps):
    
    m = len(maps)
    n = len(maps[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def bfs(start_x, start_y, end_x, end_y):
    	# 거리 정보를 저장하는 배열. 시작점에서 닿을 수 없는 경우 -1의 값을 가짐
        dist = [[-1] * n for _ in range(m)]
        Q = deque([(start_x, start_y)])
        dist[start_x][start_y] = 1
        
        while Q:
            cur_x, cur_y = Q.popleft()
            for k in range(4):
                nx = cur_x + dx[k]
                ny = cur_y + dy[k]
                
                # 배열 인덱스를 벗어나는 경우
                if nx < 0 or nx >= m or ny < 0 or ny >= n:
                    continue
                    
                # 벽인 경우
                elif maps[nx][ny] == 0:
                    continue
                    
                # 한 번도 방문하지 않은 경우만 큐에 추가
                # 최단거리로 방문하려면 같은 블럭을 두 번 이상 방문하는 일은 없어야 한다.
                if dist[nx][ny] == -1:
                    dist[nx][ny] = dist[cur_x][cur_y] + 1
                    Q.append((nx, ny))
                    
        return dist[end_x][end_y]
    
    return bfs(0, 0, m-1, n-1)