파이썬으로 폭 우선 탐색

개요

atcoder등에서 폭 우선 탐색의 문제가 나왔을 때에, 깨끗이 참조하기 위한 기사입니다.
자세한 설명은 켄쵸씨의 기사 등을 보는 것이 좋다고 생각합니다.
라고 할까, 폭 우선 탐색에 대해서 처음 배우는 분은, 꼭 상기의 기사를 먼저 읽어, Python의 실장 부분만 참고로 받을 수 있으면 다행입니다.

폭 우선 탐색에 대해서

폭 우선 탐색이란, 그래프나 나무 구조를 탐색하는 알고리즘으로, 탐색을 개시한 점으로부터 가까운 순서로 탐색해 가는 방법입니다.
(대조적인 방법으로 깊이 우선 탐색이 있고, 여기는 막다른 길이 될 때까지 경로를 돌아오지 않고 탐색하는 방법입니다.)
이미지가 매우 하기 쉬운 알고리즘이므로, 조속히 구현해 가고 싶습니다.



이미지 인용 소스 : Wikipedia

구현 방법

우선, 그래프를 인접 리스트(모르는 분은 @ell 님의 기사 등을 읽어 주세요.)등으로 받습니다.

계속해서, 시점에 인접하고 있는 정점으로부터 순서대로 탐색해 갑니다만, 여기서
1. 정점을 탐색했는지 여부의 관리
2. 탐색 예정의 정점을 포함하는 배열
의 2점이 중요하게 됩니다.

1에 관해서는, 관리할 수 없는 것과 같은 점을 탐색해 버리므로 이미지가 붙기 쉬운가라고 생각합니다.
2에 관해서는, 배열등에서 찾아낸 순서에 격납해, 선두로부터 요소를 꺼내는 것이 좋을 것입니다.

여기서, 배열의 선두로부터 요소를 꺼낼 때에, 통상의 배열(python에서는 list)을 사용하면(자), 조작 1회에 대해서, 배열의 길이분의 처리가 필요하게 되어 버립니다.
즉, 길이 N의 list에 대해서, 선두를 꺼내는 pop에 필요한 계산량은 $O(N)$가 됩니다.
이것은, 통상의 배열의 경우, 선두의 요소를 꺼내면(자), 다른 요소를 하나씩 어긋나게 할 필요가 있는 것에 기인합니다.

전치가 길어져 버렸습니다만, 이 선두의 요소를 꺼내기에 적합한 것이 큐라고 하는 데이터 구조입니다.
이 큐를 사용하여,
1. 탐색 예정의 정점을 관리한다
2. 시작점부터 순서대로 탐색을 하고, 탐색되지 않은 점이 있으면 큐에 추가
를 반복하면 폭 우선 탐색을 구현할 수 있습니다.
또, 계산량은 N개의 정점으로부터 M개의 변을 조사할 때, $O(N+M)$로 나타낼 수가 있습니다.

그럼 실제로 아래의 문제를 예로 들어 코드를 살펴 보겠습니다.

폭 우선 탐색

문제 개요

스타트에서 골까지의 최단 거리를 출력한다.

sample.py

# キューをインポート
from collections import deque

# 入力を受け取る。座標の調整のため、スタート地点とゴール地点の座標を-1する。
R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy -= 1
sx -= 1
gy -= 1
gx -= 1

# 迷路の情報を配列Gで受け取る
G = [input() for _ in range(R)]

# キューをQに入れ、スタート地点を追加
Q = deque()
Q.append([sy, sx])

# 未訪問と始点からの距離を管理するdistを定義。スタート地点に0を代入。
dist = [[-1]*C for _ in range(R)]
dist[sy][sx] = 0

# 今回は移動する４方向を事前に用意した。
dirc = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# キューの要素がなくなるまで処理を繰り返す。
while len(Q) > 0:
  y, x = Q.popleft()

# 移動先で繰り返し処理
  for dy, dx in dirc:
    y2 = y + dy
    x2 = x + dx

# 移動先が迷路の範囲内でなければ、continue
    if not (0 <= y2 < R and 0 <= x2 < C):
      continue

# 移動先が壁だったら、continue
    if G[y2][x2] == "#":
      continue

# 移動先が未訪問なら移動前の距離＋１をdistに入れて、キューに移動先の座標を追加
    if dist[y2][x2] == -1:
      dist[y2][x2] = dist[y][x] + 1
      Q.append([y2, x2])

# ゴールの距離を出力
print(dist[gy][gx])

끝에

폭 우선 탐색은, 문제로의 활용은 물론, 이 알고리즘을 응용한 것이 많이 출제되고 있습니다.

꼭, 이 기사를 읽은 후에 다른 분의 해설 기사나, @e869120 씨가 쓰여진 분야별 초중급자가 풀어야 할 과거문정선 100문

지금까지 읽어 주셔서 감사합니다.