[프로그래머스] 코딩테스트 연습 - 게임 맵 최단거리(Python)

문제 설명

문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (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

입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

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

프로그래머스

Level2 문제입니다. DFS/BFS 문제의 대표격인 문제로 유명한데요, 이전에도 자주 접했던 유형 중 하나인 문제였습니다. 이번 계기에 이런 유형을 어떻게 푸는지 한 번 정리해보겠습니다. 이 문제는 BFS를 이용해서 최단경로를 어떻게 찾아내는지가 관건인 문제입니다. 

 

DFS는 스택을 활용한 재귀라면, BFS는 큐를 사용하는 것이 특징인데요, 이 문제에서도 큐를 사용하면서 하나하나 미로를 탐색하듯이 최종 목적지로 향하는 문제라고 해석하면 됩니다.

 

먼저 파이썬에서 큐를 사용하기 위해서는 collections의 deque을 활용하는 것이 대표적입니다. 왼쪽과 오른쪽의 선입선출 방향을 자유자재로 할 수 있고 여러 함수들을 가지고 있기 때문이죠.

BFS에서 큐를 사용하는 방법은 아래와 같습니다.

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내고(popleft()) 인접 노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리
3. 큐에 노드가 없을 때까지 2번 과정 반복하기

나머지 풀이는 전체 코드를 보면서 확인해볼게요!

from collections import deque

def solution(maps):
    
    N = len(maps)   # 행
    M = len(maps[0])    # 열
    dr = [-1,1,0,0] # 행 - 상 하 좌 우 
    dc = [0,0,-1,1] # 열 - 상 하 좌 우
    
    answer = 0 
    
    def bfs(r,c):
        queue = deque([(r,c)])   # 시작 위치 (0,0)
        
        while queue:
            
            r, c = queue.popleft()
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                if 0 <= nr < N and 0 <= nc < M: # 좌표가 범위 안에 들어오면
                    if maps[nr][nc] == 1: # 갈 수 있는 길이고, 방문하지 않은 길이라면,
                        # 방문하지 않은 리스트를 따로 만들어 줄 필요없이, 갈 수 있는 길의 값이 1이므로,
                        # 방문했다면 1은 아닐 것이다.
                        maps[nr][nc] = maps[r][c] + 1
                        queue.append((nr,nc))
            # print(queue,maps[r][c])
            
        return maps[N-1][M-1]
    
    
    answer = bfs(0,0)
    
    return -1 if answer == 1 else answer

출발 시작점이 (1,1) 이라고 문제에서 했지만, 인덱싱 계산상 (0,0)으로 시작하도록 하겠습니다. 항상 BFS/DFS문제 등의 그래프 문제를 풀 때는 동, 서, 남, 북 방향에 따라 바뀌는 행과 열의 상태를 담는 리스트가 필요한데요. 나중에 방향에 따라 어떤 행과 어떤 열인지를 계산할 때 필요하기 때문입니다.

 

여기서는 각각 dr과 dc 리스트가 이에 해당합니다. 

(상, 하 , 좌, 우) 총 4방향으로 움직일 수 있으므로 방향에 따른 행과 열의 변화를 담은 것인데요,

예를 들어 "상"(북쪽)인 경우에 행은 -1이 되고, 열은 그대로 이므로 (행,열)은 각각 (-1,0)이라고 할 수 있습니다.

"우"(동쪽)인 경우에는 행은 그대로이고, 열은 1 증가하겠죠? 그럼, (행,열)은 (0,1)이 되는 것입니다.

즉, 상하좌우를 기준으로 행은 (-1,1,0,0) 로 행이 변하고, 열은 (0,0,-1,1) 로 열이 변한다는 것을 알 수 있습니다.

 

본격적으로, maps를 탐색할 것인데, 이 문제는 벽은 0으로 갈 수 있는 길은 1로 표현되었습니다. 물론 방문하는 리스트를 따로 만들어도 상관없지만, 저는 해당 자리를 방문했는지 안했는지를 나타내는 visited와 같은 리스트를 따로 만들지 않았습니다.

왜냐하면, 이 문제는 1과 0으로만 이루어진 maps이기 때문에, maps[행][열]의 값이 1이 아니라면, 자연스럽게 이미 방문한 위치가 되기 때문입니다. 방문했다면 해당 위치의 maps[행][열]의 값이 1이 아니라 다른 값으로 변했겠죠.

 

큐에 시작점을 넣고, 큐가 빌 때 까지 반복문을 돕니다. 행과 열의 위치값을 뽑아내서, 해당 위치값으로부터 4방향으로 탐색할 때, 탐색위치가 맵(maps)의 범위를 벗어나면 그대로 계속 진행하고, 범위 안이라면 이제 그 값이 무엇인지 비로소 판단할 수 있습니다.

그 값을 판단하는 부분인 maps[nr][nc] 가 1 이라면 갈 수 있는 길 중에서도 아직 방문하지 않은 곳이라는 것을 알 수 있습니다. 

maps[nr][nc] = maps[r][c] + 1
queue.append((nr,nc))

근데, 이 부분이 이해가 잘 가지 않는다구요? 

문제에서 현재 찾고자 하는 것은 좌상단 출발점인 (1,1) (계산상 (0,0)) 에서

상대팀이 있는 곳인 우하단 (N,M) (계산상(N-1,M-1)) 로 가는 최단 거리 입니다.

즉, 한 칸 씩 전진하고 이동할 때마다 거리가 1씩 증가하는 것은 "각 자리의 값+1" 을 하는 것과 같은 셈입니다.

 

다시 말하자면, maps는 벽을 제외한 갈 수 있는 길은 오직 1로만 이루어져 있고, 시작점에서의 maps값도 역시 1이므로,

한 칸씩 전진해서 거리를 1 증가시키는 것은 지금 현재 위치에 있는 값에서 이동하고자 하는 위치의 값을 더하는 것과 같다고 할 수 있습니다. 이동하고자 하는 위치의 값은 아직 탐색하지 않은 자리이기에 역시 값이 초기값 1 일테니까요.

 

이렇게, 한 칸 씩 이동하다보면 결국 마지막 우하단의 최종 종착지에서의 값은 처음부터 이동해온 거리값과 같게 될 것입니다. 답은 maps[N-1][M-1] 인 셈이죠.

 

문제에 나와 있는 예시를 해당 코드로 밟아보면서 끝까지 돌려보면,

해당 maps의 값은 아래 그림처럼 될 것입니다.

위 예시는 최종 목적지까지 갈 수 있기에 값을 제대로 출력할 수 있겠지만, 갈 수 없는 경우는 -1을 출력해야 합니다.

갈 수 없는 경우는 어떤 경우일까요?

결국, 최종 목적지가 갈 수 없다면 최종목적지 주변이 벽으로 감싸져있다는 것이므로, BFS로 진행했는데도,

maps[N-1][M-1]의 값이 초기값인 1 이라면, 해당 maps에서는 최종 목적지까지 도달할 수 없는 경우가 되겠습니다.

return -1 if answer == 1 else answer

그래서, answer == 1 이라면 -1 을 1이 아니라 다른 값이라면 곧, 그 값이 답입니다.