미로탈출

 

문제

1 - 가능한 위치, 0 - 괴물일 때,

(0, 0)에서 (n, m)까지 이동하는데 가장 짧은 거리

 

 

유형 파악

그래프가 주어지고 특정 노드의 위치를 탐색하는 것이므로 우선, BFS/DFS 이다.

 

 

코드

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

from collections import deque
def bfs(array, visited, start):
    visited[start[0]][start[1]] = True
    queue = deque()
    queue.append(start)

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]
            if next_x < 0 or next_x >= len(array) or next_y < 0 or next_y >= len(array[0]):
                continue
            if visited[next_x][next_y] == False and array[next_x][next_y] == 1:
                visited[next_x][next_y] = True
                array[next_x][next_y] = array[x][y] + 1
                queue.append([next_x, next_y])
                if next_x == len(array)-1 and next_y == len(array[0])-1:
                    return 1

array = [
    [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]
]
start = [0, 0]
visited = [[False]*len(array[0]) for _ in range(len(array))]
bfs(array, visited, start)