LV 2: 게임 맵 최단 거리

문제 링크

LV 2: 게임 맵 최단 거리

구현 방식

• bfs로 풀어주었다

코드

from collections import deque

def solution(maps):
    N = len(maps); M = len(maps[0])
    
    dx = (0, 0, -1, 1)
    dy = (-1, 1, 0, 0)
    
    def bfs(x, y):
        queue = deque([]); queue.append((x, y))
        visit = [[0] * M for n in range(N)]; visit[x][y] += 1
        
        while queue:
            x, y = queue.popleft()
            if (x, y) == (N-1, M-1):
                return visit[x][y]
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if maps[nx][ny] == 1 and visit[nx][ny] == 0:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))
        return -1
    
    result = bfs(0, 0)
    return result