[프로그래머스] Lv2 - 게임 맵 최단거리 (파이썬)

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

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

 

from collections import deque

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


def solution(maps):
    global N, M
    N = len(maps)+1
    M = len(maps[0])+1
    maps = [[0]*(len(maps[0]))]+[[0]+map for map in maps]
    return bfs(maps)


def bfs(maps):
    q = deque()
    q.append((1, 1))
    visited = [[0] * M for _ in range(N)]
    visited[1][1] = 1
    while q:
        x, y = q.popleft()
        if (x, y) == (N-1, M-1):
            return visited[x][y]
        for k in range(4):
            nx = x+dx[k]
            ny = y+dy[k]
            if 1 <= nx < N and 1 <= ny < M and maps[nx][ny] == 1:
                if not visited[nx][ny]:
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx, ny))
    return -1

 

BFS
1. 좌표가 1, 1에서 시작해서 maps를 맞춰 주었다. (그냥 0, 0에서 시작하면 될 것을...)
2. bfs 리턴
    - 길(1) 일 때만 이전 방문 + 1을 처리하면서 bfs를 돌려준다.
    - 목표지점에 도착했을 시 해당 방문 값 return
    - 도착하지 못하고 끝이 나면 -1 리턴