이코테 - 미로탈출

전형적인 BFS풀이 

위와같은 맵에서 0,0 에서 시작하여 오른쪽 맨 밑의 출구로 나가는 미로를 탈출하는데 최소한으로 움직여야하는 거리를 측정하기

한칸 움직일때마다 +1 이며, 0은 막힌공간임을 의미한다. 

 

 

 

# 미로탈출

from collections import deque
maps=[
    [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]
]
n,m = len(maps),len(maps[0])
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(x,y):
    que = deque()
    que.append((x,y))
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx==n-1 and ny==m-1 : 
                print('skip')
                return maps[x][y]+1
            if nx < 0 or ny < 0 or nx >= n or ny >= m : continue
            if maps[nx][ny]==0:
                continue
            if maps[nx][ny]==1:
                maps[nx][ny] = maps[x][y]+1
                que.append((nx,ny))
    return maps[n-1][m-1]
print(bfs(0,0))
maps