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

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

프로그래머스

 

from collections import deque

def bfs(maps):
    # 방향 벡터: 상, 하, 좌, 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    n, m = len(maps), len(maps[0])
    visited = [[0] * m for _ in range(n)]

    # 큐 초기화 및 시작점 방문
    queue = deque()
    queue.append((0, 0, 1))  # (x, y, 거리)
    visited[0][0] = 1

    while queue:
        x, y, dist = queue.popleft()

        # 상대 팀 진영에 도달하면 거리 반환
        if x == n - 1 and y == m - 1:
            return dist

        # 상하좌우 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 맵 범위를 벗어나지 않고, 이동 가능하며, 방문하지 않았을 때
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = 1  # 방문 처리
                queue.append((nx, ny, dist + 1))  # 거리 증가

    # 도착하지 못한 경우
    return -1

def solution(maps):
    return bfs(maps)