프로그래머스 (Level 2) : 게임 맵 최단거리/ Python/ 너비 우선 탐색(BFS, deque)

문제

프로그래머스

 

출처 : 프로그래머스

 

그림과 같이 N*M 맵에서좌측 맨 상단에서 우측 맨 하단까지 갈 수 있는 최단거리를 출력하는 문제이다.

맵에서 0인 구간은 못가고 1인 구간만 갈 수 있으며 목적지까지 도달할 수 없으면 -1을 출력한다.

 

주의할 점은 N,M은 같을 수도 다를 수도 있다.

 

큐를 사용해 BFS로 풀었고 이동한 거리는 현재 지점+1로 계산했다.

BFS 개념 복습하기 좋은 문제인 것 같다.

 

 

입출력 예

maps 배열	return
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

 

 

 

풀이

from collections import deque

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def solution(maps):

    n = len(maps)
    m = len(maps[0])
    
    dq=deque()
    dq.append((0,0))
    
    while dq:
        cx, cy = dq.popleft()
        
        if cx==n-1 and cy==m-1: 
            #for m in maps: print(m)
            return maps[cx][cy]
        
        for i in range(4):
            nx = cx+dx[i]
            ny = cy+dy[i]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny]==1:
                dq.append((nx,ny))
                maps[nx][ny] = maps[cx][cy]+1

    return -1