게임 맵 최단거리 - Python, deque, bfs

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

프로그래머스

 

 

 

풀이 - 나의 생각

전형적인 BFS 입문 문제라고 생각합니다.

 

que에 시작 위치를 넣고

 

상하좌우를 살피면서

 

이동하는 거리를 저장해가다가

 

원하는 위치에 도달하면 그 값을 retrun해줍니다.

 

dfs랑 다르게

 

그 위치에 도달한 첫번째 값이 최단 거리이기 때문입니다.

 

코드

 

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    
    que = deque([(0,0)])
    di = [(-1,0), (1, 0), (0, -1), (0, 1)]
    
    while que:
        x, y = que.popleft()
        
        if x == n-1 and y == m-1:
            return maps[x][y]
        
        for dx, dy in di:
            nx, ny = x+dx, y+dy
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m or maps[nx][ny] != 1:
                continue
            
            maps[nx][ny] = maps[x][y]+1
            que.append((nx,ny))
            
    return -1

 

 

 

 

 

 

 

다음에 또 봐요