##深さ優先探索をやってみたかった
つい最近、AtCoder Typical Contest というものがあることを知りました。
どうやら深さ優先探索など、競技プログラミングをやる上で必要になってくるアルゴリズムのコーディングを練習できるものみたいですね。
↓僕が今回取り組んだのはこちら↓
ATC001
##実際に書いたコード
ATC001のA問題で僕が提出したコードは以下の通りです。
def dfs(px,py):
if px < 0 or py < 0 or px > w-1 or py > h-1:
return False
if c[py][px] == '#':
return False
if c[py][px] == 'g':
return True
c[py][px] = '#'
if dfs(px-1,py):
return True
if dfs(px,py-1):
return True
if dfs(px+1,py):
return True
if dfs(px,py+1):
return True
return False
h,w = map(int,input().split())
c = []
for i in range(h):
s = input()
x = s.find('s')
if x != -1:
start = [x,i]
c.append(list(s))
sx = int(start[0])
sy = int(start[1])
if dfs(sx,sy):
print('Yes')
else:
print('No')
そもそもこれが深さ優先探索になっているのか良くわかってません。
他の方はスタックやキューを定義して回答されてましたので、これが良い回答ではないことは確かですね。
##入力例は全て突破したが。。。
AtCoderで回答する際、回答を提出する前に2〜5個ぐらいある入力例をテストコードに突っ込んでちゃんと動作するか確認しますよね。
そこは全て希望通りの出力を得ることができました。
「よっしゃキタ！」
って思ったのですが、回答した結果、以下のようになりました。
「めちゃくちゃエラー出てますやん！」
なんでこうなってしまったか悩みまくって夜しか寝れませんでした。
##Pythonでは再帰関数の呼び出し回数に上限がある
結論から先に言うと、こういうことでした。
Pythonでの再帰関数の呼び出し回数の上限は、デフォルトでは1000回だそうです。
上のコードだと完全に1000回を超えてしまいますので、それでエラーが出てたみたいですね。
##解決策
**sys.setrecursionlimit(n)**というものを書いてあげることで、再帰関数の呼び出し上限をn回に設定できます。
ということで完成したコードは次のようになります。
import sys #追加
sys.setrecursionlimit(500*500) #追加
#ここからはさっきと同じ
def dfs(px,py):
if px < 0 or py < 0 or px > w-1 or py > h-1:
return False
if c[py][px] == '#':
return False
if c[py][px] == 'g':
return True
c[py][px] = '#'
if dfs(px-1,py):
return True
if dfs(px,py-1):
return True
if dfs(px+1,py):
return True
if dfs(px,py+1):
return True
return False
h,w = map(int,input().split())
c = []
for i in range(h):
s = input()
x = s.find('s')
if x != -1:
start = [x,i]
c.append(list(s))
sx = int(start[0])
sy = int(start[1])
if dfs(sx,sy):
print('Yes')
else:
print('No')
これで無事、ACを取ることができました。
##まとめと余談
競技プログラミングを始めてまだ1ヶ月ぐらいしか経ってないため、こういう細かい部分をよく知っていなかったです。。。
もっと勉強が必要ですね。
そもそももっと良いdfsのコードの書き方があるので、こういうコードを書いた時点でアウトだったのかも・・・。
ちなみに、上のコードをPyPyで実行するとTLEになります。
ざっくりと言うとPyPyは再帰関数と相性が良くないみたいです。
ではまた。