5-2. DFS/BFSナビゲーションアルゴリズム

教材アルゴリズム動作手順図を参照

1. DFS

✓DFSとは何ですか。

深さ優先検索.1つのアルゴリズム

は、グラフィック内で深さ優先ナビゲーションを行うために使用される.

スタックデータ構造に基づく/再帰関数の利用↑

操作中のアクセス処理:スタックに挿入されたノードの操作を処理しない

ナビゲーション順序:1-2-7-6-8-3-4-5(通常は小数から)
(ナビゲーションノードに戻ると、そのノードをスタックから取り出す)

.

def dfs(graph, v, visited):
  #현재 노드 방문 처리
  visited[v] = True
  print(v, end=' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:  #해당 노드를 방문하지 않았다면 재귀호출 방문
      dfg(graph, i, visited)
      
 graph= [
   [],  #노드는 1부터 시작이므로 리스트의 0번 인덱스는 비워둠
   [2,3,8],
   ...
 ]
 
 #각 노드가 방문된 정보를 리스트 자료형으로 표현
 visited = [False]*9 #0번 인덱스를 비우기위해 8+1개 선언
 
 dfs(graph,1,visited)

✓問題：冷凍飲料

題:NxMサイズの氷棚では、穿孔した部分が0、仕切りがある部分が1と表示されています.穿孔した部分は上下左右に接しており、つながっているとみなされます.氷棚で生成されたアイスクリームの数を求めるプログラムを作成します.

key
深度優先dfsアルゴリズムを使用して、すべての接続ノード

を検索

0に接続するノードは、後でカウント

を繰り返すことを避けるためにアクセス処理を行う.

上、下位機ノードをチェックするときに再帰関数

を呼び出す.

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

#2차원 리스트로 맵 정보 받기
graph = []
for i in range(n):
	graph.append(list(map(int, input())))

#DFS구현
def dfs(x,y):
  #범위를 벗어나면 즉시 종료
  if x<=-1 or x>=n or y<=-1 or y>=m:  #리스트이므로 인덱스 주의(0시작)
    return False:
  #아직 방문하지 않은 0이라면
  if graph[x][y]==0:
    graph[x][y] = 1  #해당 노드 방문 처리
    dfs(x-1,y)       #상하좌우 위치 재귀적으로 호출
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
    return True
  return False
  
#모든 노드(위치)에 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    if dfs(n,m) == True:
      result += 1

print(result)

2. BFS

✓BFSとは何ですか。

幅優先ナビゲーション(Breadth-First Serach)近接ノード優先ナビゲーション

から

キューリソース型(先入先出)ベース

動作:ナビゲーション開始ノードをキューに入れ、アクセス処理->キューから取り出し、そのノードの隣接ノードのすべての未アクセスノードをキューに入れる->

を繰り返す

最短距離
上図bfsナビゲーション順序:1-2-3-8-7-4-5-6

from collections import deque

#bfs구현
def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True #현재 노드를 방문 처리
  #큐 전체를 반복
  while queue:
    v = queue.popleft()  #큐에서 원소를 하나씩 뽑아 출력, 주변 노드 확인
    print(v, end=' ')
    #해당 노드와 연결된 방문 이전인 노드들은 모두 큐에 넣기
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True
        
graph= [
   [],  #노드는 1부터 시작이므로 리스트의 0번 인덱스는 비워둠
   [2,3,8],
   ...
 ]
 
 #각 노드가 방문된 정보를 리스트 자료형으로 표현
 visited = [False]*9 #0번 인덱스를 비우기위해 8+1개 선언
 
 bfs(graph,1,visited)

✓問題：迷宮を脱出する

題:NxMサイズの矩形迷路に閉じ込められている.現在位置(1,1)出口は(N,M)である.モンスターがいる部分は0で、モンスターがいない部分は1です.脱出する最短経路欄の個数を求める.開始セルと最後のセルも個数に含まれます.

key
最短経路

を探す必要があるためbfsアルゴリズム

を用いる.

パスカウント+1下

の処理を続行する必要がある場合は、

の2つの状況を考慮してください.

from collections import deque

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

#이동할 네 방향 정의
dx=[0,0,+1,-1]
dy=[-1,+1,0,0]

#bfs구현
def bfs(x,y):
  queue = deque()
  queue.append((x,y))
  
  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      #미로 찾기 공간 벗어나면 무시
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      #벽인 경우 무시
      if graph[nx][ny] == 0:
        continue
      #처음 방문하는 1에 대해서만 최단 기록에 추가
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y]+1  #카운트+1
        queue.append((nx,ny))
        
   return graph[n-1][m-1]
   
print(bfs(0,0))