競プロ初中級者100問

ABC007C 幅優先探索

この記事で使うアルゴリズム

幅優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc007/tasks/abc007_3

この問題は幅優先探索を用いて解くことができます。

幅優先探索はキューによって実装できます。

Pythonの場合、キューはqueue.Queueやcollections.dequeを利用すると良いでしょう。いずれも標準ライブラリです。

この記事ではqueue.Queueを用います。

方針

  • キューを作成する。キューの各要素は（y座標、z座標、スタート地点からの距離）として利用していく。
  • キューにスタート地点をenqueueする。
  • 幅優先探索を行う。具体的には、以下の処理をキューが空になるまで繰り返す。
    • dequeueする
    • 訪問済みの場合は無視する
    • 未訪問の場合
      • 訪問フラグを立てる
      • 移動可能かを確認し、enqueueする

ポイント

訪問済みかどうかの確認はenqueueする前には必須である。

この問題の場合、dequeueした後には必須ではないが確認するべきだと思われる。
（スタート地点からの距離が等しいマスが、同じマスを複数回enqueueする可能性があり、queueのサイズが肥大化するためTLEやMLEのリスクが増える）

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利
R, C = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
maze = []
visited = [ [0]*C for _ in range(R)]
for r in range(R):
    s = input()
    maze.append(s) # 二次元リストにせず、文字列のリストのままでOK
q = queue.Queue()
q.put((sy-1,sx-1,0)) # スタート地点をenqueue
while(not q.empty()):
    y, x, d = q.get()
    if x == gx-1 and y == gy-1: # ゴールにたどり着いたら終了
        ans = d
        break
    if visited[y][x] == 1: # 訪問済みの場合は無視する
        continue
    else:
        visited[y][x] = 1 # 訪問フラグを立てる
        for dx, dy in  dxdy:
            if (0<= x+dx < C) and (0<= y+dy < R): # 範囲内に収まっているか               
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.': # 見訪問かつ通行可能か
                    q.put((y+dy,x+dx,d+1)) # 距離を+1してenqueue
print (ans)

記事情報

  • 投稿日：2020年4月16日
  • 最終更新日：2020年5月8日