Python 再帰関数 returnの性質

Question

実現したいこと

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

前提

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

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

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

該当のソースコード

import sys
 
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())

masu = [tuple(map(int, input().split())) for _ in range(H)]

check = set()
cnt = 0

def dfs(x,y):
    if masu[y][x] in check:
        #print(check)
        return
    check.add(masu[y][x])
    if x == W-1 and y == H-1:
        #print("flag")
        global cnt 
        cnt += 1
        return
    
    if x < W-1:
        dfs(x+1, y)
    if y < H-1:
        dfs(x, y+1)
    
    check.remove(masu[y][x])

dfs(0,0)
    

試したこと

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

import sys
 
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())

masu = [tuple(map(int, input().split())) for _ in range(H)]

check = set()
cnt = 0
depth = 0
def dfs(x,y, depth):
    depth += 1
    print(depth)
    global cnt 
    if masu[y][x] in check:
        #print(check)
        cnt += 0
        return
    check.add(masu[y][x])
    
    if x == W-1 and y == H-1:
        #print("flag")
        cnt += 1
        return
    
    if x < W-1:
        dfs(x+1, y, depth)
    if y < H-1:
        dfs(x, y+1, depth)
    
    check.remove(masu[y][x])

dfs(0,0,0)
    
#print(cnt)
 

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

Comments

[unadondaisuki]

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

Answer 1

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

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

Comments

[unadondaisuki]

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