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

728x90

문제설명

본 문제는 게임 맵에서 왼쪽 위에서 오른쪽 아래로 가는 가장 짧은 거리를 구하는 문제이다.

게임 시작 시, 캐릭터는 (1, 1) 위치에 있고 상대편 진영은 (5, 5)에 위치한다.

이동은 동, 서, 남, 북 순서로 하며 벽이 있거나 맵 밖으로 나가는 경우는 이동할 수 없다.

위 그림에선, 상대편 진영으로 갈 수 있는 방법은 아래의 두가지가 존재한다.


11번의 이동을 통해 도착	15번의 이동을 통해 도착

이 두 경우에서, 1번 경로보다 빠르게 이동할 수 있는 방법은 없기 때문에 정답은 11이 된다.

하지만 모든 경우에 도달할 수 있는 것은 아니다.

아래와 같은 경우 캐릭터는 상대방 진영으로 이동할 수 없다.

결국 문제에서 요구하는 것은 상대편 진영(우측 최하단)에 도착하기 위해 거쳐가야 하는 모든 칸의 수를 계산하여 출력하면 된다.

도달할 수 없는 경우엔 -1을 리턴한다.

제한사항

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

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

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

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

입출력의 경우 아래와 같다.

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

문제해설

해당 문제는 BFS 알고리즘을 통해 해결했다.

문제를 읽으면 아래와 같은 사항을 고려할 수 있다.

1. 도달하는 경로는 여러 개가 될 수 있다.

2. 게임맵의 크기는 입력에 따라 달라진다. (따로 입력을 받는 것이 아니다.)

3. 게임 캐릭터는 동서남북으로 이동한다.

4. 이동할 수 없는 경우가 존재하며 이 때 -1을 리턴한다.

이렇게 간단하게 구상하였을 때 생각한 방법은 BFS (넓이 우선 탐색) 방법이었다.

따라서 이러한 방법과 dx, dy를 사용하여 문제를 쉽게 해결했다.

코드는 아래와 같다.

정답코드

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    
    queue = deque()
    queue.append((0, 0))

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if maps[nx][ny] == 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx, ny))
            elif maps[nx][ny] > maps[x][y] + 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx, ny))
    if maps[n-1][m-1] == 1:
        return -1
    return maps[n-1][m-1]

알고리즘의 순서는 아래와 같다.

1. 시작점을 큐에 삽입한다.

2. 큐에서 점을 뽑아서 동, 서, 남, 북의 이동 경로에 대한 정보를 확인한다.

2-1. 벽이 있거나 이동할 수 없는 경로인 경우는 무시한다.

2-2. 이동가능한 경로일 때, 현재까지의 칸 수에 1을 더한 값을 넣어준다.

2-2-1. 만약 현재까지의 거리보다 더 작은 값이라면, 지금 경로에서의 이동거리 값으로 변경해준다.

3. 2번을 큐에 데이터가 없을 때까지 반복한다.

4. 마지막 경로가 한 번도 방문되지 않았다면 -1을 리턴한다.

5. 적 기지까지의 거리값을 리턴한다.

2-2-1은 이동경로가 여러개가 나올 수 있기 때문에 무시하지 않고 고려하여 계산식에 추가했다.

이렇게 보면 알고리즘 몇 개만 익혀둔다면 문제를 해결하는 난이도가 많이 낮아질 것 같다.