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

2024년 7월 5일

문제 링크 : 프로그래머스 - 게임 맵 최단거리

---

문제 접근

 
한 칸을 이동하는 과정을 한 턴 이라고 이야기하겠다.
 
적진(지도의 맨 오른쪽 맨 아래 위치)으로 가는데 필요한 최소한의 턴을 구하는 문제이다.
 
이 문제는 1일차에 [0, 0]에서부터 바이러스가 하루에 주변 한 칸씩 퍼질 때  [n - 1, m - 1]은 며칠차에 감염되는가? 와 같은 문제이다.

문제를 풀기 위해선 다음과 같은 접근 방식이 필요하다.
 

한 턴에 갈 수 있는 칸은 여러 개 일 수 있다.

 
 
나는 이 문제를 BFS 방식으로 풀이할 것이다.
 
또한, 뒤에서 말할 변수들의 이름은 다음과 같은 뜻을 가지고 있다고 생각해두자.
 

queue = 다음 방문 예정인 노드들
next_v = 지금 위치에서 한 턴 뒤에 갈 수 있는 모든 노드들
distance = 시작점에서 각 현재 위치까지 소모한 턴(거리)

 
해당 화살표 위치에 도착했다고 가정해보자. 
 
해당 위치에서 한 턴을 소모해 오른쪽으로 한 칸, 혹은 위쪽으로 한 칸 갈 수 있다.
 
어디로 가야 최단거리인지 잘 모르니 현재 위치에서 다음 방문할 수 있는 위치를 배열 next_v에 몽땅 담아두는 것이다.
 

 

next_v = [현재 위치에서 오른쪽 좌표, 현재 위치에서 위쪽 좌표]

 
모두 담은 후, 방문할 노드를 담아놓는 queue에 다시 몽땅 담아두고 queue의 값들을 하나씩 popleft() 하며 한 거리를 이동하여 갈 수 있는 좌표의 경우의 수를 또 next_v에 몽땅 담아둔다.
 

next_v에 각 경우에 도착한 모든 좌표 정보를 담는다.

 
각 경우의 경로에서 한 턴씩 소모하며 진행을 하다, 먼저 적진에 도착하면 해당 과정까지 소모한 턴(거리)을 출력하면 된다.
 

 

 
중요한 점은, next_v에 다음 턴에 방문할 수 있는 모든 노드 정보들을 일단 다 담아두었다가, 모두 다 담았다면 queue에 해당 노드 정보들을 싹 다 옮겨담고 지금까지 움직인 거리인 distance를 1 증가시켜야 한다는 점이다.
 
이유는 각 경우의 경로에서 한 턴씩 지날 때를 계산하고 있기 때문이다.
 
이 문제에서는 적진으로 갈 수 있는 경로가 존재하지 않을 수도 있기 때문에, BFS 로직이 모두 종료되었는데도 불구하고 적진에 도착하지 못했다면 -1을 출력한다.

---

전체 코드

 

from collections import deque

def isValid(row, col):
    global visited
    global total_row
    global total_col

    if 0 <= row < total_row and 0 <= col < total_col:
        if not visited[row][col]:
            return True

    return False

def solution(maps):
    global total_row
    global total_col
    global visited

    total_row = len(maps)
    total_col = len(maps[0])

    # 북 동 남 서
    d_row = [-1, 0, 1, 0]
    d_col = [0, 1, 0, -1]

    queue = deque()
    # 다음 턴에 방문하게 될 노드들을 담을 배열
    next_v = []
    visited = [[False for _ in range(total_col)] for _ in range(total_row)]

    queue.append([0, 0])
    visited[0][0] = True

    distance = 1
    while queue:
        next_v.clear()
        while queue:
            now_row, now_col = queue.popleft()

            for i in range(4):
                next_row = now_row + d_row[i]
                next_col = now_col + d_col[i]
                if isValid(next_row, next_col):
                    if maps[next_row][next_col] == 1:
                        next_v.append([next_row, next_col])
                        visited[next_row][next_col] = True

        while next_v:
            v = next_v.pop();
            if v[0] == total_row - 1 and v[1] == total_col - 1:
                return distance + 1
            queue.append(v)
        distance += 1

    # while문 안에서 [n, m]까지 도달하지 못했다면 갈 수 없는 좌표임.
    return -1

if __name__ == "__main__":
    print(solution([[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]]))

---

풀이 후기

 
한 턴이 지날 때마다 각 경로의 다음 위치를 어떻게 모두 담나 고민을 많이 했던 문제였다.
이를 해결하기 위해 next_v 라는 배열을 따로 선언했고, 다음 위치를 모두 담았다면 queue에 next_v 요소들을 모두 옮겨담아 distance를 1 증가시켜주는 로직으로 이를 해소하였다.