1001アルゴリズム

DFSとよく出てくるのがBFSです.BFはBreath First Search,幅優先探索である.最近のノードから探索を開始する.DFSは深さであるため,可能な限り開いたノードを最初にブラウズし,BFSは逆である.BFSは、通常、キューデータ構造を使用する.アルゴリズムを記述して隣接ノードをキューに繰り返し入れると、最初に入ったノードは終了し、近いノードからナビゲートします.
1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
2)ノードをキューから取り出し,そのノードの隣接ノードの主がアクセスしていないノードをすべてキューに挿入し,アクセス処理を行う.
3)これ以上できなくなるまで.

from collections import deque

def bfs(graph, start, visited): 
#graph는 인접 리스트로 표현한 것
#start는 시작점
#visited는 방문했는지 안했는지를 T/F로 표현
#큐 구현을 위해 deque 사용
	queue = deque([start])
    #지금 있는 곳의 노드는 방문처리
    visited[start] = True
    #queue가 빌떄까지 반복
    while queue:
    	v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
graph = [ []. [2,3,8], [1,7], [1,4,3]........]
visited = [False] * 9

bfs(graph, 1, visited)
    

#脱出迷路:NxMサイズの矩形迷路と同じ.(1,1)から(N,M)まで一度に1マス移動できます.0,1ですが、1しか使えず、最も少ない格数を要求します.セルの計算には、開始セルと最後のセルが含まれます.
3 3
110
010
011 -> 5
最初の点が(1,1)の場合
(1,1),(1,2),(1,3)
(2,1),(2,2),(2,3)
(3,1),(3,2),(3,3)そうです.最短経路の場合はBFSで解決するのが望ましい.bfsは、始点に近いノードから順にグラフィック内のすべてのノードを参照するためである.
例を挙げると.
(1,1)アクセス処理を行い,(1,1)ポップアップし,周辺ノードにおいてアクセスされていない場所(1,2)をキューに入れてアクセス処理を行う.次に(2,2)をポップアップし、周囲のノードがアクセスしていない(3,2)に再び移動します.またそこで同じことをして、それから行きます(3,3).だから

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):
    queue = deque()
    queue.append((x,y))
    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))