[프로그래머스/Python] Lv 2. 게임 맵 최단거리

⭐ 문제 링크

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

프로그래머스

 

⭐ 풀이 코드

# BFS 알고리즘 : 너비 우선 탐색
# 가까운 노드부터 탐색

from collections import deque

def solution(maps):
    answer = 0
    
    # 좌, 우, 하, 상
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    r = len(maps)    # 행
    c = len(maps[0]) # 열
    
    # 좌표 방문 최단거리
    graph = [[-1 for _ in range(c)] for _ in range(r)]
    
    queue = deque()
    queue.append((0, 0))  # 시작점
    graph[0][0] = 1      
    
    while queue:
        # 현재 위치
        y, x = queue.popleft()
        
        # 현재 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]  # 이동 후 x좌표
            ny = y + dy[i]  # 이동 후 y 좌표
            
            # 이동 후 좌표가 범위 내에 있는 경우 and 벽이 아닌 경우 
            if (0 <= nx < c) and (0 <= ny < r) and (maps[ny][nx]==1):
                # 해당 좌표를 처음 방문하는 경우에만 최단 거리 기록
                if graph[ny][nx] == -1:
                    graph[ny][nx] = graph[y][x] + 1
                    queue.append((ny,nx))
    
    
    return graph[r-1][c-1]