python~幅優先探索とキュー

初めに

どうもKeymaleです。かなり久しぶりの投稿です。今回は幅優先探索について説明します。幅優先探索をするうえで便利なキューというデータ構造についても説明します。

幅優先探索

今回、幅優先探索をする上で迷路でのスタートからゴールまでの最短経路探索を例題に行いたいと思います。

素晴らしい題材がatcoderにあったので載せておきます。

インプットとして以下が与えられます。

R C
sy sx
gy gx
c(1,1)c(1,2) … c(1,C)c(1,1)c(1,2) … c(1,C)
c(2,1)c(2,2) … c(2,C)c(2,1)c(2,2) … c(2,C)
:
c(R,1)c(R,2) … c(R,C)c(R,1)c(R,2) … c(R,C)

Rは迷路の行数、Cは迷路の列数、sx, syはスタート地点の座標、gx, gyはゴールの座標を表しています。c(x, y)は迷路の形状を示しており、c(x, y)＝”#”の時x, yの座標の位置は壁になります。例題としてこんな感じの迷路の入力が与えられます。

7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

幅優先探索ではスタート地点の(2, 2)から一つ移動したところのから１マスで移動できるところを探索し、その後その１マスで移動できるところすべてから１マス移動できるところをつまり２マス移動できるところを探索し、次に２マス移動できるところすべてから人ます移動できるところ、つまり３マス移動できるところ、、、、

というように移動できるマス単位で探していくので、幅優先探索と言われています。この探索をすれば必ず最短での経路を検索することができます。

キュー

幅優先探索において、どこのマスが何マスで移動できるかを記録し、調べたところは重複して調べないようにするためにキューを使います。

キューはFirst In First Outと呼ばれ、データを入れた順番でしか取り出せない構造となります。pythonでは以下のように使います

from collections import deque
a = deque([(1,2)])
print(a)
>>deque([(1, 2)])
a.append((2,3))
print(a)
>>deque([(1, 2), (2, 3)])
b = a.popleft()
print(b)
>>(1, 2)
print(a)
>>deque([(2, 3)])

基本的にはappendで追加し、popleftでデータを取り出します。これを用いて幅優先探索を実装しましょう

実装例

実装例を以下に記載します。

from collections import deque
INF = 0xffffffff

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

R, C = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())

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

c = [input() for i in range(R)]
cost = [[INF] * C for i in range(R)]
cost[sy][sx] = 0
q = deque([(sx, sy)])
while q:
  x, y = q.popleft()
  c2 = cost[y][x] + 1
  for i in range(4):
    x2 = x + dx[i]
    y2 = y + dy[i]
    if x2 < 0 or x2 >= C  or y2 < 0 or y2 >= R or c[y2][x2] == "#":
      continue
    if cost[y2][x2] > c2:
      cost[y2][x2] = c2
      q.append((x2, y2))
ans = cost[gy][gx]
print(ans)

入力例を入れて、実行すると１１を返します。これは、スタートからゴールまで最短１１マスで行けることを示しています。ここら辺がスラスラできるようになると入門卒業レベルではないでしょうか？そのうち深さ優先探索も載せていきたいと思います。

最後まで見ていただきありがとうございました。