[Level 2] 게임 맵 최단거리

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

코딩테스트 연습 - 게임 맵 최단거리

---

접근

(0, 0)에서 출발하여 (N-1, M-1)까지 BFS를 실행하여 최단거리를 찾는다.

 

구현

- 2차원 리스트인 dist에 거리를 저장한다.

- (N-1, M-1)에 저장된 값을 최종적으로 출력하며, 만약 0일 경우 -1을 출력하도록 한다.

    q = deque()
    N = len(maps)
    M = len(maps[0])
    dist = [[0 for _ in range(M)] for _ in range(N)]
    
    q.append((0, 0))
    dist[0][0] = 1

- BFS를 실행한다.

- 현재 위치가 (N-1, M-1)일 경우 탐색을 종료한다.

- 도착지가 아닐 경우 현재 위치에서 상하좌우를 검사하여 1이고 범위 내에 있을 때 이동한다.

- 이동하면서 다음 위치의 거리를 현재 까지의 거리 + 1로 저장한다.

    while q:
        cy, cx = q.popleft()
        if cy == N-1 and cx == M-1:
            break
        
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx, N, M) and dist[ny][nx] == 0:
                if maps[ny][nx] == 1:
                    q.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx] + 1

- answer에 dist[N-1][M-1]의 값을 저장한다.

- 이때 answer가 0이라면 갈 수 없기 때문에 answer에 -1을 저장한다.

    answer = dist[N-1][M-1]
    if answer == 0:
        answer = -1

---

전체 코드

from _collections import deque

def check_range(y, x, N, M):
    return (0 <= y < N) and (0 <= x < M)

def solution(maps):
    answer = 0
    
    q = deque()
    N = len(maps)
    M = len(maps[0])
    dist = [[0 for _ in range(M)] for _ in range(N)]
    
    q.append((0, 0))
    dist[0][0] = 1
    
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    while q:
        cy, cx = q.popleft()
        if cy == N-1 and cx == M-1:
            break
        
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx, N, M) and dist[ny][nx] == 0:
                if maps[ny][nx] == 1:
                    q.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx] + 1
                    
    answer = dist[N-1][M-1]
    if answer == 0:
        answer = -1
    return answer