[programmers] 게임 맵 최단거리

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

코딩테스트 연습 - 게임 맵 최단거리

 

 

전형적인 BFS 문제!

from collections import deque

def solution(maps):

    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    n ,m = len(maps), len(maps[0])
    q = deque()
    q.append((0,0))
    
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx < 0 or nx >= n or ny<0 or ny>= m or maps[nx][ny]== 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y]+1
                q.append((nx,ny))
    
    # if maps[n-1][m-1] ==1:
    #     return -1
    # else:
    #     return maps[n-1][m-1]
    return maps[n-1][m-1] if maps[n-1][m-1] != 1 else -1

※ 포인트

bfs로 가장 최단 거리를 찾는 방법

맨 마지막 행 마지막 열이 끝이기 때문에 그 값을 하나씩 더해가며 거리 update