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

문제 링크

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

프로그래머스

 

문제 설명

각 팀이 출발지부터 상대 팀 진영을 먼저 파괴하면 이기는 게임의 문제이다. 각 팀은 상대 팀 진영에 최대한 빨리 도착해야 한다. 캐릭터는 동, 서, 남, 북으로 움직일 수 있으며, 게임 맵을 벗어난 길은 갈 수 없다. 상대 팀이 벽을 세워두었다면 그 길로 갈 수 없다. 상대 팀 진영에 도착할 수 없을 때는 -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) 위치에 있습니다.

 

풀이

(1, 1)부터 도착지까지 가장 빠르게 도착하는 길을 return하는 것이기 때문에 BFS를 이용하여 deque에 x 위치, y위치, 이동한 횟수를 넣고 방문 리스트를 만들어 갔었던 길을 다시 가지 않게 했고 도착지에 도착하면 cnt를 return, 도착하지 못하면 -1을 리턴하도록 했다.

 

✅ Code - 성공

from collections import deque

di, dj = ((1,-1,0,0), (0,0,1,-1))

def solution(maps):
    
    n = len(maps)
    m = len(maps[0])
    v = [[0] * m for _ in range(n)]
    
    q = deque()
    q.append([0,0,1])
    while q:
        x, y, cnt = q.popleft()
        if x == n-1 and y == m-1:
            return cnt
        
        for i in range(4):
            dx, dy = x + di[i], y + dj[i]
            if 0 <= dx < n and 0 <= dy < m:
                if not v[dx][dy] and maps[dx][dy] != 0:
                    v[dx][dy] = 1
                    q.append([dx, dy, cnt+1])   
    
    return -1