Pythonで巨大な迷路から脱出できるかを判定するアルゴリズム

問題の概要

100万行 × 100万列という非常に大きなグリッドを考えます。グリッド上には、移動できない「ブロックされたセル」のリストが与えられています。

私たちはスタート地点（source）から出発し、ゴール地点（target）を目指します。1回の移動ごとに、ブロックされていないセルの中から上下左右に隣接するマスへ進むことができます。

求めたいのは、「一連の移動によってゴールに到達することが可能かどうか」の判定です。

たとえば、入力が blocked = [[0,1],[1,0]]、source = [0,0]、target = [0,3] の場合、出力は False になります。

解法のアプローチ

この問題を解くためには、次の手順に従います。

• blocked のすべてのセルをセット（集合）に変換して保持します。

• dfs() メソッドを定義します。引数は x、y、target、seen です。

• (x, y) がグリッドの範囲外にある、blocked に含まれている、またはすでに seen に含まれている場合は False を返します。

• (x, y) を seen に追加します。

• seen のサイズが 20000 を超えた場合、または (x, y) が target と一致した場合は True を返します。

• 上下左右の4方向に対して再帰的に dfs を呼び出し、その結果を OR で返します。

• 最後に、「source から target への探索」と「target から source への逆向きの探索」の両方が成功した場合にのみ True を返します。

なぜ 20000 なのか？

ブロックされるセルの数は最大でも 200 個程度とされています。200 個のセルで完全に囲める領域の面積は、最大でも約 19,900 セル（200 × 199 ÷ 2）しかありません。つまり、探索したセル数が 20,000 を超えているなら、その地点は確実に閉じ込められていないと判断できます。これにより、100万 × 100万という巨大なグリッド全体を走査することなく、計算量を大幅に抑えられるのです。

実装例

class Solution(object):
    def isEscapePossible(self, blocked, source, target):
        blocked = set(map(tuple, blocked))
        def dfs(x, y, target, seen):
            if not (0 <= x < 10**6 and 0 <= y < 10**6) \
               or (x, y) in blocked or (x, y) in seen:
                return False
            seen.add((x, y))
            if len(seen) > 20000 or [x, y] == target:
                return True
            return dfs(x + 1, y, target, seen) or \
                   dfs(x - 1, y, target, seen) or \
                   dfs(x, y + 1, target, seen) or \
                   dfs(x, y - 1, target, seen)
        return dfs(source[0], source[1], target, set()) and \
               dfs(target[0], target[1], source, set())

ob = Solution()
print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))

入力

[[0,1],[1,0]], [0,0], [0,3]

出力

False

まとめ

このアルゴリズムの鍵となるのは、深さ優先探索（DFS）と「探索済みセル数の上限」を組み合わせた発想です。さらに、スタートとゴールの双方から探索を行うことで、片方向だけでは見逃してしまうケースにも対応できます。巨大なグリッドを相手にしても、現実的な計算量で正確な判定が可能になる、非常にスマートな手法だと言えるでしょう。