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

프로그래머스

 

코드

from collections import deque    
        
def solution(maps):
    n, m = len(maps), len(maps[0])
    
    queue = deque()
    queue.append((0, 0)) # 시작 위치 큐에 추가
    
    # 상하좌우
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    # BFS
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # nx, ny가 maps 범위 안에 있는지 확인
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] == 0: continue
                if maps[nx][ny] == 1: # 벽이 없으면 이동거리 +1, 새로운 위치 큐에 추가
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))

    if maps[n-1][m-1] > 1:
        return maps[n-1][m-1]
    else: # (n,m)으로 이동 불가하면(=제자리이면 1)
        return -1

기본적인 DFS/BFS 문제이다.

문제에서 최단거리를 구하라고 했기 때문에 BFS로 해결했다.

 

BFS는 큐를 이용하기 때문에 deque를 사용했고, 처음 시작 위치인 (0, 0)을 큐에 추가해 주었다.

queue = deque()
queue.append((0, 0)) # 시작 위치 큐에 추가

그다음, 시작위치에서 상하좌우로 이동이 가능한지 판별해야 하기 때문에 상하좌우 이동을 dx, dy로 나타냈다.(x: 행, y: 열)

# 상하좌우
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

이제 while문을 사용해 BFS를 구현한다.

# BFS
while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # nx, ny가 maps 범위 안에 있는지 확인
        if 0 <= nx < n and 0 <= ny < m:
            if maps[nx][ny] == 0: continue
            if maps[nx][ny] == 1: # 벽이 없으면 이동거리 +1, 새로운 위치 큐에 추가
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx, ny))

먼저, queue에서 좌표 하나를 가져와 x, y로 저장하고 상하좌우로 이동한다.

이동한 좌표 nx, ny가 maps의 범위 안에 있는지 확인한다.

maps는 n x m 형태이므로 행의 범위는 0에서 n-1까지, 열의 범위는 0에서 m-1까지이다.

문제에서 0은 벽이고, 1은 벽이 아니라고 했으므로, (nx, ny)가 이동 가능한 좌표이면 기존 위치까지의 이동거리+1 값을 (nx, ny)의 이동 거리로 저장하고 큐에 새로운 위치를 추가해 계속해서 while문을 반복한다.

 

모든 과정이 끝나면, (n-1, m-1)에는 최단 이동 거리가 저장되어 있을 것이다.

하지만, 이동이 불가능한 위치였으면 주어진 maps 그대로 (n-1, m-1)에는 1이 저장되어 있게 된다.

따라서, 1인지 아닌지 구분하여 조건에 맞게 리턴값을 지정해 주면 된다.

if maps[n-1][m-1] > 1:
    return maps[n-1][m-1]
else: # (n,m)으로 이동 불가하면(=제자리이면 1)
    return -1