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

---

문제설명

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

코딩테스트 연습 - 게임 맵 최단거리

사고과정

• 전형적인 BFS 유형 문제였다. 2차원 배열이 주어질 때, 특정 시작점에서 도착점까지의 최단거리 비용을 구하는 것이였다. 
• 큐를 활용했고 방문 테이블을 따로 정의해주어서 방문 테이블을 방문 여부 체크와 거리 이동 칸 수를 계산하는 용으로 활용했다. 그리고 주어진 maps 테이블을 활용해서 벽인지 아닌지 체크했다.
• 도착하지 못하는 경우는 큐가 빌 경우이므로, while안에서 중간에 break 하지 않고 while 조건문에 위배가 되서 무한 루프가 끝날 경우에 수행되는 else 구문 즉, while ~ else 구문을 활용했다.

풀이

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def solution(maps):
    # 칸 수 기록할 맵
    n = len(maps)
    m = len(maps[0])
    visited = [[0] * m for _ in range(n)]
    
    # 시작점 큐에 넣기
    x, y = 0, 0
    visited[x][y] = 1
    queue = deque([(x, y)])
    
    while queue:
        x, y = queue.popleft()
        
        if x == n-1 and y == m-1:
            return visited[n-1][m-1]
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] == 1 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1 
                    queue.append((nx, ny))
    else:
        return -1