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

문제 설명

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

프로그래머스

간단하게 문제를 설명해보자면

위 그림과 같이 5 x 5 크기의 맵이 있다면, 캐릭터가 (1,1) 위치에 있을 때 상대 팀 진영은 (5,5)에 위치합니다.

검은색 부분은 막혀서 갈 수 없는 길이며, 흰색 부분으로만 캐릭터가 이동할 수 있습니다.

캐릭터가 움직일 때는 동,서,남,북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

게임 맵의 상태 maps가 주어질 때, 캐릭터가 상대 맵 진영에 도착하기 위해 지나가야 하는 칸의 개수의 최솟값을 리턴해야 합니다.

제한사항

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.

n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

처음에 캐릭터는 게임 맵의 좌측 상단인 (1,1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n,m) 위치에 있습니다.

문제 풀이

모든 경로를 탐색하면서 가장 빠른 경로를 찾아야 하므로 BFS 알고리즘을 이용합니다.

BFS를 구현하기 위해 필요한 기본 요소로는

• 큐(deque): 탐색할 좌표를 저장
• 방문 조건: 이미 방문했거나 벽인 경우를 처리
• 이동 방향: 상하좌우 탐색

가 있지만, 이 문제에서는 visited 배열 대신 주어진 maps 배열을 활용합니다.

maps 배열 자체를 방문 여부와 이동 거리 저장용으로 사용할 수 있습니다.

if maps[nx][ny] == 1: # 아직 방문하지 않은 경우 -> 방문하면 1이 아닌 다른 숫자로 바뀜
   maps[nx][ny] = maps[x][y] + 1 # 이동 거리 저장 (방문 처리)
   queue.append((nx,ny))

최종 코드

from collections import deque

def solution(maps):
    answer = 0
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    n,m = len(maps), len(maps[0])
    
    def bfs(x,y):
        queue = deque([(x,y)])

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

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

								# 맵 범위 안에 있고, 벽이 아니며 아직 방문하지 않은 경우
                if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx,ny))
                    
        # 최종 도착점 (n-1, m-1)의 값이 변경되었다면 도달 가능하므로 그 값을 반환
				# 값이 여전히 1이라면 도달하지 못했음을 의미하므로 -1 반환
        return maps[n-1][m-1] if maps[n-1][m-1] > 1 else -1
                
    return bfs(0,0)