[백준/python]2178번 미로탐색 - bfs

prev에 경로를 저장하고 BFS를 돌렸다. BFS가 끝나면 prev를 거꾸로 돌아가며 지나온 개수를 구한다. 돌아가는 과정이 비효율적이다.

from collections import deque

N, M = map(int, input().split())
miro=[[0 for _ in range(M) ] for _ in range(N)]
for i in range(N):
    line=input()
    for j in range(M):
        miro[i][j]=int(line[j])

visited=[[0 for _ in range(M) ] for _ in range(N)]
visited[0][0]=1
q=deque([])
q.append([0,0])

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


prev=[[0 for _ in range(M) ] for _ in range(N)]

while (q):
    x,y=q.popleft()
    if x==N-1 and y==M-1:
        break
    
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and miro[nx][ny]==1: 
            prev[nx][ny]=(x,y)
            visited[nx][ny]=1
            q.append([nx,ny])

a=N-1
b=M-1    
sol=1
while True:
    sol+=1
    if prev[a][b]==(0,0):
        break
    a,b=prev[a][b]
print(sol)

visited 배열에 숫자를 누적하며 계산하는 방법을 사용해보자.