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

프로그래머스 문제 보러가기

from collections import deque

def solution(maps):
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    n = len(maps)
    m = len(maps[0])

    queue = deque()
    
    # 시작점인 (0,0)을 큐에 추가 . (0,0)은 미로의 시작 위치
    queue.append((0, 0))

    while queue:
    
        # x,y 변수는 상하좌우로 인접한 노드들을 탐색하는데 사용 
        x, y = queue.popleft()

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

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            if maps[nx][ny] > 1 or maps[nx][ny] == 0:
                continue

            if nx == 0 and ny == 0:
                continue

            queue.append((nx, ny))
            maps[nx][ny] += maps[x][y]

    return maps[n-1][m-1] if maps[n-1][m-1] > 1 else -1

[풀이]

• 이 코드는 미로 문제를 해결하는 함수인 solution 이다. 미로는 2차원 배열 'maps'로 주어지며, 0과 1로 구성되어 있다. 0은 벽을 나타내고 1은 이동가능한 공간을 나타낸다.
• 함수는 미로의 시작점인 (0,0)에서 미로의 마지막 지점인 (n-1, m-1) 까지 도달하는 최단 경로의 거리를 반환하며, 만약 도달할 수 없다면 -1을 반환한다.

[해결방법]
너비 우선 탐색(BFS)를 사용하여 최단 경로를 찾는다. 큐를 이용하여 BFS를 구현하였다.

• 너비 우선탐은, 시작 노드에서 인접한 노드들을 모두 방문한 후, 방문한 노드들과 인접한 노드들을 차례대로 방문하는 방식이다. 큐(queue)자료구조를 사용하여 구현하며, 먼저 들어온 노드를 먼저 방문하여 최단 경로를 찾는다.

dx, dy: 이동할 수 있는 방향을 나타내는 리스트

1. 우선 함수는 주어진 미로의 크기를 파악하여 'n'과 'm'에 저장, 'n'은 행의 개수이고 'm'은 열의 개수
2. BFS를 위해 큐를 생성하고, 시작점인(0,0)을 큐에 넣는다.
3. BFS 루프를 시작하고, 큐가 비어있지 않은 동안 다음을 반복
   a. 큐에서 좌포(x,y)를 꺼내고, 현재 위치에서 상하좌우로 이동한 좌표를 계산 (nx, ny)
   b. 범위를 벗어난 좌표인 경우 무시하고 다음 이동을 처리
   c. 벽인 경우 무시하고 다음 이동 처리
   e. 이미 방문한 곳이거나, 시작점인 경우, 무시하고 다음 이동 처리
   위 조건들을 통과한 좌표 (nx, ny) 를 큐에 넣고, 해당 좌표에 도달하는 최단 거리를 갱신
   -> BFS 루프가 종료되면, maps[n-1][m-1] 에는 시작점에서 도착점까지의 최단 거리가 저장되어 있고 이 값을 반환한다. 도달할 수가 없는 경우 -1을 반환

• 시간복잡도 : O(n * m)
  -> 여기서 n은 미로의 행의 개수이고, m은 미로의 열의 개수