Level 2. 게임 맵 최단거리

10. 게임 맵 최단거리

코딩테스트 연습 > 찾아라 프로그래밍 마에스터 > 게임 맵 최단거리
https://programmers.co.kr/learn/courses/30/lessons/1844

---

문제 설명

Input value

• maps = $n*m$ 크기의 0과 1로 구성된 리스트

Output value

• $[0, 0]$에서 $[n-1, m-1]$까지 도달하기 위한 최소 거리

• 리스트의 0은 통과하지 못하며, 1은 통과 가능하다.

• 도달하지 못하는 경우 -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) 위치에 있습니다.

---

문제 구상

#00
maps = [[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]]

1. 맵에서 움직일 수 있는 4 방향을 정의한다.

#01
dx,dy = [-1,1,0,0],[0,0,-1,1]

2. -1 으로 구성되어 있는 n x m 크기의 맵을 재구성하고, 시작지점의 값을 1로 설정한다.

#02
m = len(maps)
n = len(maps[0])

nmap = [[-1 for i in range(n)] for _ in range(m)]
nmap[0][0] = 1

현재 위치를 정의하고, BFS를 통해 위치와 위치의 맵값을 갱신한다.
즉, 마지막 위치인 $maps[-1][-1]$의 값이 거리를 의미하며, 만약 BFS를 통해 갱신되지 않을 경우(도달하지 못하는 경우) -1 값이 return 하게 된다.

#03
from collections import deque 
locate = deque()
locate.append([0,0])
while locate:
    y,x = locate.popleft()
#04
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]

        if 0 <= ny < m and 0 <= nx < n and maps[ny][nx]==1:
            if nmap[ny][nx] == -1:
                nmap[ny][nx] = nmap[y][x] + 1
                locate.append([ny,nx])
nmap[-1][-1]

---

문제 풀이

from collections import deque

def solution(maps):
    dx,dy = [-1,1,0,0],[0,0,-1,1]
    m,n = len(maps),len(maps[0])
    
    new_map = [[-1 for _ in range(n)] for _ in range(m)]
    new_map[0][0] = 1
    
    locate = deque()
    locate.append([0,0])
    
    while locate:
        y,x = locate.popleft()
        
        for i in range(len(dx)):
            ny,nx = y+dy[i],x+dx[i]
            
            if 0<= nx < n and 0<= ny < m and maps[ny][nx] == 1:
                if new_map[ny][nx] == -1:
                    new_map[ny][nx] = new_map[y][x]+1
                    locate.append([ny,nx])
                    
    return new_map[-1][-1]