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

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

ただいまの
回答率

89.64%

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 162

Saikohage

score 1

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

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

#僕の解答(メモリ消費が少し大きい)

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 'No'
H, W= map(int, input().split())
f = [list(input()) for i in range(H)]

def dfs(i,j):
    global ans
    global f
    if f[i][j] == 'g': ans = 'Yes'
    f[i][j] = '#'
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    for l in range(len(di)):
        ni = i + di[l]
        nj = j + dj[l]
        if 0 <= ni and ni < H and 0 <= nj and nj < W and f[ni][nj]!= '#':
            dfs(ni, nj)

for i in range(H):
    for j in range(W):
        if f[i][j] == 's': 
            dfs(i,j)
print(ans)

それに対し

#正答となるコード(メモリ消費が若干低い)


import sys
sys.setrecursionlimit(1000000)


def dfs(x, y):
    d[x][y] = 1

    # 移動4方向をループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # nx と ny が街の範囲内か、行ったことがないか、塀ではないかを判定
        if 0 <= nx and nx < n and 0 <= ny and ny < m and d[nx][ny] == 0 and c[nx][ny] != "#":
                dfs(nx, ny)


n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

# 到達したかどうか(0は未到達、1は到達済み)
d = [[0] * m for i in range(n)]

# 移動する4方向
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# スタート地点から dfs を始める
for i in range(n):
    for j in range(m):
        if c[i][j] == "s":
            dfs(i, j)

# ゴール地点に到達したかどうか
for i in range(n):
    for j in range(m):
        if c[i][j] == "g" and d[i][j]:
            print("Yes")
            exit()
print("No")
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+2

di dj の分のメモリ×再帰回数
が違いますね


(追記)
実際に di dj をモジュールのグローバルなオブジェクトにするだけで MLE が出なくなることが確認できます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/01/17 08:47

    >>> [1, 0, -1, 0].__sizeof__()
    72
    >>> 72 * 2
    144

    1回の再帰で 144バイト + 変数辞書領域 が増えますね。

    キャンセル

  • 2020/01/23 04:31

    @quiquiさん、@shiracamusさん、お答えいただきありがとうございました。おかげ様で解決しました。

    キャンセル

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

  • ただいまの回答率 89.64%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る