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

문제

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

풀이

풀이 1 - (런타임 에러)

1. 코드는 dx와 dy 두 개의 리스트를 정의합니다. 이 리스트들은 각각 상, 하, 좌, 우 네 방향으로 이동할 때의 x와 y 좌표 변화를 나타냅니다. 나중에 주변 셀을 확인하는데 사용될 것입니다.
2. bfs 함수는 출발점부터 목적지까지의 최단 경로를 찾기 위해 너비 우선 탐색(BFS)을 수행합니다.
3. bfs 함수는 세 개의 매개변수를 받습니다: x, y, maps. x와 y는 시작 좌표를 나타내고, maps는 게임 맵을 나타냅니다.
4. bfs 함수 내에서 deque를 이용해 큐를 초기화합니다. 시작 지점 (x, y)을 큐에 넣습니다.
5. BFS의 메인 루프가 시작됩니다. 큐가 빌 때까지 계속됩니다.
6. 코드는 dx와 dy 리스트를 사용하여 네 방향 (상, 하, 좌, 우)을 반복합니다.
7. 각 방향에 대해 현재 좌표 x와 y를 기반으로 새로운 좌표 nx와 ny를 계산합니다. 새로운 좌표 nx와 ny가 게임 맵의 범위 내에 있는지 확인합니다. 좌표가 맵의 경계를 벗어난 경우 해당 위치는 무시합니다.
8. 좌표가 맵의 경계 내에 있지만 벽인지(값이 0인지) 확인합니다. 벽인 경우에도 해당 위치는 무시됩니다. 벽을 통과할 수 없기 때문입니다. 좌표가 이동 가능한 셀(값이 1인 셀)인 경우, 그 위치의 값을 현재 거리에 1을 더한 값으로 업데이트합니다. 이 단계는 해당 셀에 도달하는 최단 거리를 기록하는 데 중요합니다.
9. 새로운 위치 (nx, ny)는 큐에 넣어 BFS 프로세스를 계속합니다.BFS 프로세스는 모든 도달 가능한 셀을 방문할 때까지 계속됩니다.
10. BFS가 완료된 후, 함수는 목적지인 (len(maps) - 1, len(maps[0]) - 1) 지점이 도달 가능한지 확인합니다. 목적지가 도달 불가능한 경우 해당 지점의 값이 여전히 1인 것입니다. 이 경우 함수는 -1을 반환합니다.
11. 만약 목적지가 도달 가능하다면, 함수는 목적지 지점의 값을 반환합니다. 이 값은 목적지에 도달하기 위한 최단 경로를 나타냅니다.

from collections import deque

# 방향 리스트 생성
dx = [-1, 1, 0, 0]  # 상 하 좌 우
dy = [0, 0, -1, 1]

def bfs(x, y, maps):  # 시작점
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        # 현 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어나는 경우 무시
            if not (0 <= nx < len(maps) and 0 <= ny < len(maps[0])):
            # if nx < 0 or ny < 0 or nx >= len(maps) or ny >= len(maps[0]):
                continue
            # 벽인 경우
            if maps[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx, ny))
    
    # 목적지에 도착가능한지 확인
    if maps[len(maps) - 1][len(maps[0]) - 1] == 1:
        return -1
    
    # 가장 오른쪽 아래까지 최단 거리 반환
    return maps[len(maps) - 1][len(maps[0]) - 1]

def solution(maps):
    return bfs(0, 0, maps)