2178-미로탈출

<문제>

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

<풀이>-BFS알고리즘 사용

• 출발위치를   queue에 넣는다.
• queue에 넣은 원소를 추출한다음 해당원소의 인접노드중 이동가능한 노드를 queue에 넣는다.
• 이동가능한 노드를 queue에 삽입하고 이동거리를 +1해준다.
• 위의 2,3번째 과정을  queue가 빌때까지 계속 반복해준다.

<코드-파이썬>

from collections import deque

n,m = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
graph = []
for i in range(n):
    graph.append(list(map(int,input())))
def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    #queue가 빌때까지 반복
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx,ny))
    return graph[n-1][m-1]


print(bfs(0,0))