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

from collections import deque
def solution(maps):
    
    n,m = len(maps), len(maps[0]) # 행 개수, 열 개수
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    visited = [[False]*m for _ in range(n)]
    
    queue = deque([(0,0)])
    
    visited[0][0] = True
    
    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < m and not visited[nx][ny] and maps[nx][ny] != 0:
                queue.append((nx,ny))
                maps[nx][ny] = maps[x][y] + 1
                visited[nx][ny] = True
    
    if maps[n-1][m-1] == 1:
        return -1
    else:
        return maps[n-1][m-1]

이번 문제는 주어진 게임 맵의 (0,0) 좌표에서 (n-1,m-1) 좌표로 가기 위한 최소한의 이동 칸 수를 구하는 문제이다.

 

2차원 배열로 주어진 값과 '최소 이동 거리'라는 키워드를 보자마자 완전 탐색 알고리즘 중에서 BFS를 떠올릴 수 있었고, 한 칸씩 이동할 때마다 현재 좌표 값에 +1 을 저장해주는 방식으로 풀이하였다.

 

BFS 알고리즘을 복습해볼 수 있었던 좋은 문제였다 :)