質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Q&A

解決済

1回答

582閲覧

Python 再帰関数 returnの性質

unadondaisuki

総合スコア4

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

0グッド

1クリップ

投稿2023/04/09 05:19

編集2023/04/09 06:02

実現したいこと

PythonにてDFS(再帰)を用いて、特定の条件を満たすルートを全て洗い出したいです。

前提

Atcoder で以下の問題をDFS(再帰)を用いて解きたいと考えています。
https://atcoder.jp/contests/abc293/tasks/abc293_c

発生している問題・エラーメッセージ

下に自分の書いたコードを添付します。
17行目で”ゴールに辿り着いた際、一段階戻って他の経路の探索を続ける”ことができないです。
ですが、returnを取り外すと継続できます。
また13行目で行っている、”条件に合わなかった場合、一段階戻って他の経路の探索を続ける”についてはreturnがついていても可能です。
これはなぜなのでしょうか。
returnにはどのようなルールがあるのか理解できずにいます。

該当のソースコード

python

1import sys 2 3sys.setrecursionlimit(10**7) 4 5H, W = map(int, input().split()) 6 7masu = [tuple(map(int, input().split())) for _ in range(H)] 8 9check = set() 10cnt = 0 11 12def dfs(x,y): 13 if masu[y][x] in check: 14 #print(check) 15 return 16 check.add(masu[y][x]) 17 if x == W-1 and y == H-1: 18 #print("flag") 19 global cnt 20 cnt += 1 21 return 22 23 if x < W-1: 24 dfs(x+1, y) 25 if y < H-1: 26 dfs(x, y+1) 27 28 check.remove(masu[y][x]) 29 30dfs(0,0) 31

試したこと

再帰の深さの遍歴を確認しました。
returnをつけてもゴールには規定回数(3回)たどり着けているようですが、カウントが1回だけになっているようで、ここに原因があるようですが理由まではわかりませんでした。。。

python

1import sys 2 3sys.setrecursionlimit(10**7) 4 5H, W = map(int, input().split()) 6 7masu = [tuple(map(int, input().split())) for _ in range(H)] 8 9check = set() 10cnt = 0 11depth = 0 12def dfs(x,y, depth): 13 depth += 1 14 print(depth) 15 global cnt 16 if masu[y][x] in check: 17 #print(check) 18 cnt += 0 19 return 20 check.add(masu[y][x]) 21 22 if x == W-1 and y == H-1: 23 #print("flag") 24 cnt += 1 25 return 26 27 if x < W-1: 28 dfs(x+1, y, depth) 29 if y < H-1: 30 dfs(x, y+1, depth) 31 32 check.remove(masu[y][x]) 33 34dfs(0,0,0) 35 36#print(cnt) 37
3 3 3 2 2 2 1 3 1 5 4
1 2 3 3 4 4 5 2 3 4 4 5 3 4 5

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

unadondaisuki

2023/04/09 05:36

試行したことを追記しました。
guest

回答1

0

ベストアンサー

ゴール判定の前に現在のマスの値をcheckに追加してしまっているのが原因です。
ゴール判定でreturnするので、追加したものが削除されず、後の判定ですべて通過済みになってしまいます。
この処理を、ゴール判定の後に移動してみてください。

returnを外すと回るのは、その後のif文が素通りして、追加したものが削除されようになるからです。

投稿2023/04/09 07:06

TakaiY

総合スコア12968

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

unadondaisuki

2023/04/09 10:39

仰せの通りでした。 ご教示頂きありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問