[BFS] 프로그래머스 Lv2. 게임 맵 최단거리 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

최단거리를 구하기 위해 BFS를 사용한다.

이때 상하좌우로 이동하면서 맵을 탐색해야 한다. 따라서 변화량을 나타내는 dx와 dy 리스트를 생성한다.

 

초기 시작 위치를 (0, 0)으로 지정하고, 시작 위치에서부터 상하좌우로 탐색한다. 탐색하면서 조건문을 통해 맵을 벗어나지 않는지, 벽이 아닌지, 방문한 적이 없는지 확인한다.

위 조건을 모두 만족할 경우 방문 처리를 수행하고, 맵의 현재 위치에 거리를 업데이트한다.

 

모든 탐색을 마친 후 최종 도착지까지의 거리가 1이면 상대팀 진영에 도착하지 못한 경우이므로 -1을 리턴하고, 거리가 1이 아닐 경우 도착지까지의 최단 거리를 리턴한다.

 

😎 내 코드

from collections import deque

def solution(maps):
    N = len(maps)
    M = len(maps[0])

    visited = [[False] * (M) for _ in range(N)]
    
    dx = [1, -1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]
    
    def BFS():
        queue = deque()
        queue.append((0, 0))
        visited[0][0] = True
        
        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:  # 맵을 벗어나지 않는지 확인
                    if maps[nx][ny] and not visited[nx][ny]:  # 맵이 벽이 아니면서 방문한 적 없는지 확인
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                        maps[nx][ny] = maps[x][y] + 1  # 거리 업데이트
            
    BFS()
    
    if maps[N-1][M-1] == 1:
        return -1
    else:
        return maps[N-1][M-1]