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

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844
• Level 2

 

이 코드는 BFS를 이용하여 최단 경로를 탐색합니다.

BFS는 시작 지점에서 가까운 노드부터 탐색하기 때문에, 도착 지점에 처음 도달했을 때가 곧 최단 거리이며,

따라서

visited[n-1][m-1]

에 저장된 값이 최단 거리를 보장합니다.

또한 방문 여부를 확인하며 중복 방문을 방지하기 때문에, 불필요한 경로 탐색도 하지 않습니다.

 

from collections import deque
def solution(maps):
    
    n,m = len(maps), len(maps[0])
    dx, dy = [1,-1,0,0], [0,0,1,-1]
    
    visited = [[-1 for _ in range(m)] for _ in range(n)]
    visited[0][0] = 1
    
    queue = deque([(0,0)])
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1 and maps[nx][ny] == 1:
                queue.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1
    
    return visited[n-1][m-1]