[python] 이것이 취업을 위한 코딩테스트다 BFS - 미로탈출

from collections import deque

n, m = 5, 6

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            my = y + dy[i]
            if nx < 0 or nx >= n or my < 0 or my >= m:
                continue
            if edges[nx][my] == 0:
                continue
            if edges[nx][my] == 1:
                edges[nx][my] = edges[x][y] + 1
                queue.append((nx, my))

    return edges[n - 1][m - 1]

print(bfs(0, 0))

• python

Reference

• 해당 포스팅은 이것이 취업을 위한 코딩테스트다 책을 보고 풀이 해본 것입니다. 지적사항 있으시면 댓글 남겨주시면 감사하겠습니다.