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

문제

• nxm 게임 맵이 주어질 때, (1,1)에서 (n,m)에 도착하기 위해 지나가야 하는 최솟값을 리턴하기
  • 1 <= n, m <= 100
  • 상하좌우로 이동 가능
• 도착할 수 없다면 -1 리턴하기

 

풀이

• 전형적인 BFS 문제 (최단거리 구하기)
• 시간 복잡도 : 인접행렬일 때 $O(N^2)$ 이므로 충분하다.
• 갈 수 있는 위치(맵에서 안벗어나고) 아직 가지 않은 곳일 때 Go

 

from collections import deque
def solution(maps):
    n, m = len(maps), len(maps[0])
    dx = (-1, 1, 0, 0)      # 상, 하, 좌, 우
    dy = (0, 0, -1, 1)  
    q = deque([(0, 0, 0)])  # (x위치, y위치, 움직인 횟수)
    while q:
        x, y, cnt = q.popleft()
            
        if x == n-1 and y == m-1:   # 도착한 경우
            return cnt+1
            
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            
            # 갈 수 있는 위치이고, 아직 가지 않은 곳일 때 Go
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                maps[nx][ny] = -1
                q.append((nx, ny, cnt+1))
    
    return -1

 

 

References

• 프로그래머스 고득점Kit BFS/DFS