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

일치하기만 할 뿐, 더 나은 답이 아닙니다.

[프로그래머스 - 여행경로]

알고가기

1. BFS

• 너비 우선 탐색
• 그래프에서 가까운 노트부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조
• 그래프 이동 비용이 동일할 때, 최단시간 구하는 문제에 자주 사용

문제

n * m 크기의 맵에서 내 캐릭터가 (0,0)에 있을 때, 가장 오른쪽 아래로 가는 최단시간을 구하시오

조건

• 동,서,남,북 방향으로 한칸 씩 이동 가능
• 맵을 벗어날 수 없음
• n,m은 1이상 100이하 자연수
• n,m은 서로 다를 수도 있음
• n,m은 모두 1일 수 없음
• 맵의 0은 벽, 1은 길
• 경로가 존재하지 않는 경우 -1 return

ex

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11

나의 풀이

from collections import deque


def solution(maps):
    queue = deque()
    n, m = len(maps), len(maps[0])  # 맵의 크기 n,m
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]   # 방향 변수
    x, y = 0, 0     # 현재 위치

    time = [[0] * m for _ in range(n)]  # (0,0) 에서 해당 칸까지 시간

    queue.append((x, y))
    time[x][y] = 1
    while queue:
        x, y = queue.popleft()
        if x == n and y == m:  # 도착 시 종료
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵 안에 존재 하는 올바른 경로 인지
            if 0 <= nx < n and 0 <= ny < m:
                # 벽(0)이 아닌 길(1) + 방문 하지 않은 길
                if maps[nx][ny] == 1 and time[nx][ny] == 0:
                    queue.append((nx, ny))  #
                    # 기존 시간 + 1, 방문 시간 증가
                    time[nx][ny] = time[x][y] + 1
                    
    return time[n - 1][m - 1] if time[n - 1][m - 1] != 0 else -1

# time
# [[1, 0, 9, 10, 11],
# [2, 0, 8, 0, 10],
# [3, 0, 7, 8, 9],
# [4, 5, 6, 0, 10],
# [0, 0, 0, 0, 11]]