深さ優先探索でこのコードがもう片方よりのメモリ消費が多い理由？

AtCoderでこの深さ優先探索の問題を解いていたのですが、
AtCoderの深さ優先探索の問題
僕のコードがMLE（メモリ消費が大きすぎる）がなってしまいました。しかしネット上で見つけたある、別の方のコードはメモリ消費にならずに正答となっていました。なぜこっちの方がメモリ消費が低いのかよくわかりません。
僕のMLEとなった解答
 正答になるネットでみつけた解答
 見つけたコードのサイト

コードの違いとしては僕はdfsで僕が通った場所を'#'にしているのに対し、見つけた解答はそれをやらずに代わりにその地点を通ったかどうかを判定する配列を別に作っていて、それだけが違いのような気がします。論理的になぜ僕の解答の方がメモリを消費しているのかわかりません。どなたか教えていただければ幸いです。

Python
1#僕の解答（メモリ消費が少し大きい）
2
3from collections import defaultdict,deque
4import sys,heapq,bisect,math,itertools,string,queue,copy,time
5import numpy as np
6sys.setrecursionlimit(10**8)
7INF = float('inf')
8mod = 10**9+7
9eps = 10**-7
10def inp(): return int(sys.stdin.readline())
11def inpl(): return list(map(int, sys.stdin.readline().split()))
12def inpl_str(): return list(sys.stdin.readline().split())
13
14ans = 'No'
15H, W= map(int, input().split())
16f = [list(input()) for i in range(H)]
17
18def dfs(i,j):
19    global ans
20    global f
21    if f[i][j] == 'g': ans = 'Yes'
22    f[i][j] = '#'
23    di = [1, 0, -1, 0]
24    dj = [0, 1, 0, -1]
25    for l in range(len(di)):
26        ni = i + di[l]
27        nj = j + dj[l]
28        if 0 <= ni and ni < H and 0 <= nj and nj < W and f[ni][nj]!= '#':
29            dfs(ni, nj)
30
31for i in range(H):
32    for j in range(W):
33        if f[i][j] == 's': 
34            dfs(i,j)
35print(ans)

それに対し

Python
1#正答となるコード（メモリ消費が若干低い）
2
3
4import sys
5sys.setrecursionlimit(1000000)
6 
7 
8def dfs(x, y):
9    d[x][y] = 1
10 
11    # 移動4方向をループ
12    for i in range(4):
13        nx = x + dx[i]
14        ny = y + dy[i]
15 
16        # nx と ny が街の範囲内か、行ったことがないか、塀ではないかを判定
17        if 0 <= nx and nx < n and 0 <= ny and ny < m and d[nx][ny] == 0 and c[nx][ny] != "#":
18                dfs(nx, ny)
19 
20 
21n, m = map(int, input().split())
22c = [list(input()) for i in range(n)]
23 
24# 到達したかどうか（0は未到達、1は到達済み）
25d = [[0] * m for i in range(n)]
26 
27# 移動する4方向
28dx = [1, 0, -1, 0]
29dy = [0, 1, 0, -1]
30 
31# スタート地点から dfs を始める
32for i in range(n):
33    for j in range(m):
34        if c[i][j] == "s":
35            dfs(i, j)
36 
37# ゴール地点に到達したかどうか
38for i in range(n):
39    for j in range(m):
40        if c[i][j] == "g" and d[i][j]:
41            print("Yes")
42            exit()
43print("No")