スタックオーバーフローを回避したい

Question

深さ優先探索アルゴリズムを再帰を用いて記述してみたのですが、プロコンサイトでの判定が一部サンプルデータで実行時エラーとなり、スタックオーバーフローが発生しているのではないかと思われます。問題点及び解決方法をご教示いただけると助かります。

###問題
Atcoder Typical Contest 001 A

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

[入力]
入力は以下の形式で標準入力から与えられる。

H W
c0,0 c0,1 c0,W−1
c1,0 c1,1 c1,W−1
:
cH−1,0 cH−1,1 cH−1,W−1
1 行目には、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
2 行目からの H 行には、格子状の街の各区画における状態 ci,j(0≦i≦H−1,0≦j≦W−1) が与えられる。
i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
"s" : その区画が家であることを表す。
"g" : その区画が魚屋であることを表す。
"." : その区画が道であることを表す。
"#" : その区画が塀であることを表す。
高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
与えられた街の外を通ることはできない。
s と g はそれぞれ 1 つずつ与えられる。

[出力]
塀を 1 回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、辿りつけない場合は No を標準出力に 1 行で出力せよ。

###コード

import sys
 
h,w = list(map(int,input().split()))
M = [list(input()) for _ in range(h)]
 
for i,j in enumerate(M):
    if "s" in j:
        sr,sc = i,j.index("s")
 
def dfs(r,c):
    M[r][c] = "#"
    for i,j in ([-1,0],[1,0],[0,-1],[0,1]):
        if not (0 <= r+i < h and 0 <= c+j < w):
            continue
        if M[r+i][c+j] == "g":
            print("Yes")
            sys.exit()
        if M[r+i][c+j] == ".":
            dfs(r+i,c+j)
 
dfs(sr,sc)
print("No")

###実行結果
コードテスト
Submission #3124726

Answer 1

厳密にはスタックオーバーフローではないのですが、だいたいその認識で良いと思います。

pythonは再帰の深度を制限しています。デフォルトは1000です。

上限は以下のコードで変更できます。

import sys
sys.setrecursionlimit(適当な数字)

---

この間、同じ質問に回答していました・・・

Python 3.x - 深さ優先探索の問題でREが出てしまう(139765)｜teratail

Comments

[退会済みユーザー]

ご回答ありがとうございます！
ご指摘のとおり追記したところ、エラーをださず正答することができました。
全く同じ質問があったとのこと、見つけられておらずお手数をかけてすみません。

Pythonではデフォルトで再帰の深度を制限しており、メモリが足りていてもその制限に達した時点でエラーとなるので、その制限を明示的に緩めてあげる必要があるということですね。

ちなみになのですが、Python3ではなくPyPy3で実行した場合、以下のとおり一部サンプルで時間制限及びメモリ制限に引っかかってしまい、全体的にも実行時間が長くなりました。
[PyPy3での実行結果](https://atc001.contest.atcoder.jp/submissions/3124909)
一般的にPyPyはPythonより速いと言われているかと思うのですが、なぜ今回の場合はPyPyの方が遅くなってしまったのか、もし分かればお教えいただけると嬉しいです！
よろしくお願いします。

[hayataka2049]

よくわかりません。
軽くコードテストで触ってみた感じだと、PyPy3は今回のような再帰しまくるコードでは論外クラスで遅いみたいです。PyPy2は多少マシになるようですが（今回のコードだとinputをraw_inputにすればそのまま動くと思います）、それでもCPythonに負けてるような。
なんででしょうね。

[退会済みユーザー]

そうなんですね…、とりあえず今後は「再帰はCPython」の方針でやってみます。
ちなみに質問した後で以下のサイトを見つけたのですが、PyPyではsys.setrecursionlimit() を記述してもしなくても変わらないようですね。（リンクの貼り方わからずすみません）

https://pypyja.readthedocs.io/en/latest/cpython_differences.html
「sys.setrecursionlimit() はPyPyでは(不要であり、)無視されます。 CPythonでは、コールのネスト数の最大値を設定します。 これを超えると実行エラーが起こります。 PyPyで他の実行エラーが原因でスタックがオーバーフローし、制限はより低レベルで チェックされます。 (制限は現在768KBでハードコードされ、Linux上では大体1480 Python callに相当します。)」

ありがとうございました！