2022.02.14 [백준] (python 파이썬) 미로 탐색

 

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

2178번: 미로 탐색

---

풀이

이 문제는 최단 거리를 구하는 문제이기 때문에 bfs를 이용하여 코드를 작성했다. 문제에서 주어진 배열을 저장할 arr배열과 거리를 저장할 vis배열을 만들었다.

 

from collections import deque
 
n,m=map(int, input().split())
arr=[]
vis=[[0]*m for _ in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
 
 
def bfs(x,y):
    deq=deque()
    deq.append([x,y])
    vis[x][y]=1
    while deq:
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if vis[nx][ny]==0 and arr[nx][ny]==1:
                    deq.append([nx,ny])
                    vis[nx][ny]=vis[x][y]+1
 
 
 
for i in range(n):
    arr.append(list(map(int,input())))
bfs(0,0)
print(vis[n-1][m-1])