[Python]DFS와BFS 백준 2178

 문제

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

이런경우 bfs를 써야 풀수 있다.

dfs의 경우에는 미로의 경로가 가장 짧다고 말할 수 없다.

코드는 이전 bfs와 다르지않다. 해당 노드까지의 최소 칸수를 적어주는것 외에는 동일

하다.

import sys
from collections import deque
 
 
def find_maze(start_row,start_colume,N,M):#bfs를 통해 찾기
    q=deque()
    q.append([start_row,start_colume])
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    while q:
        [x, y] = q.popleft()
        for i in range(4):#네군데 큐담기
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and matrix[nx][ny]==1:#한번도 방문하지않았다면
                #이전에 방문하였다면 최솟값은 이전값이다.
                q.append([nx,ny])
                matrix[nx][ny]+=matrix[x][y]#해당노드까지의 칸수
 
 
 
 
N,M=map(int,sys.stdin.readline().split())
 
matrix=[]
 
for i in range(N):
    str=sys.stdin.readline()
    tmp=[]
    for i in range(M):
        tmp.append(int(str[i]))
    matrix.append(tmp)
 
 
find_maze(0,0,N,M)
print(matrix[N-1][M-1])