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

게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

프로그래머스

 

문제

풀이

• n, m: 지도의 행, 열
• visited: 방문한 곳을 표시하는 리스트, 초기는 모두 False로 할당
• BFS 탐색을 위해 deque를 초기화하고, 출발점인 (0,0)을 추가
• dx, dy 배열을 사용해 상 하 좌 우 이동 표시
• BFS 실행
  • 큐에서 현재 위치(y, x)를 꺼내고, 새로운 곳으로 이동을 시도. 이 때 조건에 따라 지도 안에서 벽이 아닌(!= 0), 아직 방문하지 않은 경우에만 진행
  • 해당 위치의 값을 +1로 설정하여 이동 거리를 지도에 기록
  • 목표 지점(n-1, m-1)의 값이 여전히 1이면 조건에 따라 -1 반환, 그렇지 않으면 총 이동 거리를 반환

from collections import deque

def solution(maps):
    n = len(maps)  # 행의 수
    m = len(maps[0])  # 열의 수
    visited = [[False] * m for _ in range(n)]

    queue = deque()
    queue.append((0, 0))  # 시작점 (행, 열)
    visited[0][0] = True  # 시작점 방문 표시

    # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        y, x = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵의 경계 내에서만 작동하도록 조건을 설정
            if 0 <= nx < m and 0 <= ny < n:
                # 다음 위치가 1이고 방문하지 않았다면
                if maps[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] = True
                    queue.append((ny, nx))
                    maps[ny][nx] = maps[y][x] + 1  # 이전 노드에서 1 증가

    # 목표 지점에 도달하지 못했다면 -1 반환
    if maps[n-1][m-1] == 1:
        return -1
    else:
        return maps[n-1][m-1]  # 목표 지점에 저장된 값 반환