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

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

프로그래머스

풀이

2차원 지도에서 출발지로부터 목적지까지의 최단거리를 알아내는 작업이므로, 전형적인 BFS 문제라고 할 수 있다. 따라서 풀이 자체도 특히 어려운 부분 없이 출발지부터 BFS를 진행하여, 목적지에 도착할 때 몇 칸 움직인 상태인지를 출력하면 되기에 간단한 편이다.

 

다만, 주의해야 할 점은 목적지에 도달하지 못한 경우에는 -1을 출력해야 한다는 점이다. 처음에 필자는 목적지에 도달하지 못하는 조건을 생각할 때, 단순히 목적지의 왼쪽과 위쪽이 막혀있는 경우로 생각하였는데 당연하게도 이는 잘못된 가정이다. 목적지에 도달하지 못하는 경우의 수는 너무나도 많기에 하나하나 그 조건을 체크하는 것은 불가능하다. 따로 불가능한 경우를 체크하는 것이 아닌, 출발지에서부터 BFS를 완료하였는데도 목적지에 도달하지 못했다면 이때가 목적지에 도달할 수 없는 경우이기에, -1을 출력하면 되는 것이다.

from collections import deque

def solution(maps):
    answer = 0
    
    # 배열이기에 zero based index이므로, 가로와 세로의 길이에서 -1을 해줘야함
    n = len(maps) - 1 
    m = len(maps[0]) - 1
    
    visited = [[0 for _ in range(m+1)] for _ in range(n+1)] # 방문 여부를 표시할 2차원 배열
    
    deq = deque([((0,0), 1)]) # BFS에 Queue로 사용할 덱 자료구조
    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 상, 하, 좌, 우로 이동하기 위해 가로, 세로에 더해줘야 할 값들 미리 정의
    
    while deq: # 덱이 빌 때까지 BFS 진행
        (x, y), step = deq.popleft() # 현재 좌표, 현재까지 거쳐온 칸의 수
        if x == n and y == m: # 만약, 현재 위치가 도착지라면 
            return step # 현재까지 거쳐온 칸의 수가 최단거리
        
        for _dir in dirs: # 현재 위치에서 상하좌우로 이동
            dx, dy = _dir
            nx = x + dx
            ny = y + dy
            
            if (nx < 0 or nx > n or ny < 0 or ny > m) or maps[nx][ny] == 0 or visited[nx][ny] == 1: # 다음 위치가 지도를 벗어나거나, 벽이거나 이미 방문한 경우라면
                continue # 더 이상 BFS를 진행하지 않음
            
            visited[nx][ny] = 1 # 다음 위치 방문 처리
            deq.append(((nx, ny), step + 1)) # 덱에 넣어서 다음 위치에서 BFS를 진행할 수 있도록 함
    
    return -1 # BFS가 완료될 때까지 목적지에 도달하지 못하였다면 -1 반환