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

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

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

BFS로 풀 수 있는 전형적인 문제입니다. 최단거리를 구해야하기 때문에 너비 우선 탐색을 진행해주고 도착점에서 결과값이 1이면 거리가 갱신되지 못한 것이므로 -1을 리턴하고, 그 외에는 도착점의 값을 리턴해주면 됩니다.

 

[풀이]

from collections import deque
dx, dy = [1,-1,0,0], [0,0,1,-1]


def bfs(maps):
    n, m = len(maps), len(maps[0])
    visited = [[False] * m for _ in range(n)] 

    q = deque()
    q.append((0,0))
    visited[0][0] = True

    while q:
        curr_x, curr_y = q.popleft()
        for i in range(4):
            nx, ny = curr_x + dx[i], curr_y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if maps[nx][ny] != 0:
                    maps[nx][ny] = maps[curr_x][curr_y] + 1
                    visited[nx][ny] = True
                    q.append((nx,ny))

    return maps[n-1][m-1] if maps[n-1][m-1] != 1 else -1


def solution(maps): 
    answer = bfs(maps)
    return answer