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

문제 정보

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

프로그래머스

 

문제 분석

(1,1) -> (n,m)으로의 최단거리를 구하는 문제입니다. (BFS 활용)

 

풀이 코드

from collections import deque

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

def is_valid_coord(y,x):
    return 0 <= y < N and 0 <= x < M

def solution(maps):
    global N, M
    N = len(maps) 
    M = len(maps[0]) 
    
    dq = deque()
    dq.append([0,0,1])
    
    while len(dq) > 0:
        y, x, d = dq.popleft()
        print(y, x, d)
        
        if y == N-1 and x == M-1:
            return d
        
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            nd = d + 1
            
            if is_valid_coord(ny,nx) and maps[ny][nx] != 0:
                maps[ny][nx] = 0 # 방문체크
                dq.append([ny, nx, nd])
    return -1