[ Lv 2 ] 게임 맵 최단거리

- bfs로 최단 경로를 찾아 준다.

- visited를 따로 두어 방문했던 정점을 다시 방문하지 않도록 함.

- bfs에서는 목적지에 처음 도달하였을 때가 최단 경로이므로 목적지에 도달하기만 하면 바로 return해주면 된다.

- queue가 비었을 때는 목적지로 갈수가 없는 케이스이므로 -1 리턴

from collections import deque

def bfs(maps):
    queue = deque()
    maxX = len(maps) - 1
    maxY = len(maps[0]) - 1
    visited = [[False] * (maxY + 1) for _ in range(maxX + 1)]
    queue.append([0, 0, 1])

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

    while queue:
        cx, cy, c = queue.popleft()
        if cx == maxX and cy == maxY:
            return c

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx <= maxX and 0 <= ny and ny <= maxY:
                if visited[nx][ny] == False and maps[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append([nx, ny, c+1])

    return -1

def solution(maps):
    return bfs(maps)

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges