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

문제 설명

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

프로그래머스

 

 

코드 구현

  

    
    
    
    
  
# 거리의 최적값 = 너비 우선 탐색 (BFS)
from collections import deque

def solution(maps):
	# 상하좌우 이동 방향
    moves = [[-1,0],[1,0],[0,-1],[0,1]]
    
    # 게임 맵의 행/열
    n = len(maps)
    m = len(maps[0]) 
    
    # 거리를 저장하는 배열 dist를 -1로 초기화
    dist = [[-1]*m for _ in range(n)]  # n*m 배열
    
    def bfs(start):
        # 시작 위치를 deque에 추가
        q = deque([start])
        dist[start[0]][start[1]] = 1  # 방문 표시
        
        while q:
            here = q.popleft()
            
            # 현재 위치에서 이동할 수 있는 모든 방향
            for direction in moves:
                row, column = here[0] + direction[0], here[1] + direction[1]
                
                # 이동한 위치가 map을 벗어난 경우 다음 방향으로 넘어감
                if row < 0 or row >= n or column < 0 or column >= m:
                    continue
                    
                # 이동한 위치에 벽이 있는 경우 다음 방향으로 넘어감
                if maps[row][column] == 0:
                    continue
                    
                # 이동한 위치가 처음 방문하는 경우, deque에 추가하고 거리 갱신
                if dist[row][column] == -1:
                    q.append([row, column])
                    dist[row][column] = dist[here[0]][here[1]] + 1
    
        return dist
    

    bfs([0,0])  # 시작 위치    

    # 목적지까지의 거리 반환, 목적지에 도달하지 못한 경우 -1 반환
    return dist[n-1][m-1]