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

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

문제 설명

프로그래머스의 게임 맵 최단거리 문제는 직사각형 모양의 맵에서 시작점(0, 0)에서 도착점(n-1, m-1)까지 이동할 때 거쳐야 하는 최소 칸 수를 구하는 문제입니다.
맵은 1과 0으로 구성되며, 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타냅니다.
상하좌우 방향으로만 이동할 수 있으며, 시작점과 도착점은 항상 1입니다.

---

문제 접근 방식

1. BFS(너비 우선 탐색) 활용
   • 시작점에서 출발하여 도착점까지 도달하는 경로 중, 가장 짧은 경로를 찾아내기 위해 BFS를 사용합니다.
2. 방문 처리
   • 방문한 칸을 추적하여 중복 방문을 방지합니다.
3. 거리 기록
   • 현재까지 이동한 거리를 maps 배열에 기록하여, 각 칸에 도달하는 데 필요한 최소 이동 횟수를 저장합니다.
4. 종료 조건
   • 도착점에 도달하면, 현재 이동 거리에서 1을 더한 값(마지막 칸 포함)을 반환합니다.
   • 도착할 수 없는 경우 -1을 반환합니다.

---

문제 풀이

from collections import deque

def solution(maps):
    answer = 0
    # n: 행의 수, m: 열의 수
    n, m = len(maps), len(maps[0])
    # 도착점 좌표
    f_x, f_y = n - 1, m - 1

    # 동, 서, 남, 북 이동 방향
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # 방문 여부를 표시할 배열 초기화 (모든 칸은 미방문 상태)
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True

    # BFS를 위한 큐 초기화
    queue = deque()
    queue.append((0, 0))

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

        # 상하좌우 방향 탐색
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]

            # 맵의 범위 체크: 범위를 벗어나면 무시
            if xx < 0 or xx >= n or yy < 0 or yy >= m:
                continue

            # 도착 지점인 경우, 현재 칸의 값에 1을 더해 최단 거리를 반환
            if xx == f_x and yy == f_y:
                answer = maps[x][y] + 1
                return answer

            # 이동 가능하고 미방문한 칸인 경우 처리
            if not visited[xx][yy] and maps[xx][yy] == 1:
                queue.append((xx, yy))
                visited[xx][yy] = True
                # 다음 칸까지의 이동 거리를 기록 (현재 칸 값 + 1)
                maps[xx][yy] = maps[x][y] + 1

    # 도착점에 도달하지 못한 경우 -1 반환
    answer = -1
    return answer

구현 시 주의사항 및 팁

• BFS 활용:
  • BFS를 사용하면 시작점에서 도착점까지의 최단 경로를 찾을 수 있으므로, 경로의 이동 횟수를 효과적으로 계산할 수 있습니다.
• 방문 처리:
  • visited 배열을 이용해 이미 방문한 칸은 중복 방문하지 않도록 하여, 불필요한 탐색을 막습니다.
• 거리 기록:
  • maps 배열에 현재까지 이동한 거리 정보를 갱신하면, 별도의 추가 배열 없이도 각 칸까지의 최단 경로 길이를 파악할 수 있습니다.
• 경계 조건 처리:
  • 맵의 범위를 벗어나는 경우를 반드시 체크하여, 인덱스 에러를 예방하세요.
• 경로 미도달 시 처리:
  • 모든 가능한 경로를 탐색한 후에도 도착점에 도달하지 못할 경우, -1을 반환해야 합니다.