[python 파이썬] 백준 2178번 미로탐색

2178번: 미로 탐색

이 문제는 BFS로 풀어야하는 문제이다. 

설명은 코드와 함께 하겠다!

 

from collections import deque

n,m=map(int,input().split())

graph=[]
for i in range(n):
    graph.append(list(map(int,input())))

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

def bfs(x,y):
    #큐 구현위해 deque라이브러리 사용
    queue = deque()
    queue.append((x,y))
    #queue가 빌때까지 반복
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            # 현재위치에서 네방향으로의 위치 확인
            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]

#BFS를 수행한 결과 출력
print(bfs(0,0))