かくれんぼをする

問題解決の考え方

グラフィック理論と幅優先ナビゲーション(BFS)

メモリオーバーフローおよびタイムアウトの防止

✔修正前コード1[メモリオーバーフロー]

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
queue = deque([])

if N == K:
    print('0')
    sys.exit()

queue.append(N+1)
if N - 1 >= 0:
    queue.append(N-1)
queue.append(2*N)

count = 0

while queue:
    ln = len(queue)
    count += 1
    for _ in range(ln):
        tmp = queue.popleft()
        if tmp == K:
            print(count)
            sys.exit()
        queue.append(tmp+1)
        if tmp - 1 >= 0:
            queue.append(tmp-1)
        queue.append(2*tmp)

事実解釈の方向性は正しい.BFSを利用して,N−1,N+1,2*Nの3つの分岐まで伸ばし続け,その後探索数に達しcount値のその解を出力する.

メモリが過剰なのは、Queueを入れる値の最大範囲を制限するのではなく、アクセスした要素をQueueに入れ続け、countが大きくなるにつれてQueueの長さが非常に大きくなるためです.そこで私はそれを補足し、コードを再提出しました.

✔修正前コード[タイムアウト]

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
queue = deque([])

if N == K:
    print('0')
    sys.exit()

visited = []    
if N + 1 <= 100000:
    queue.append(N+1)
    visited.append(N+1)
if N - 1 >= 0:
    queue.append(N-1)
    visited.append(N-1)
if 2*N <= 100000:    
    queue.append(2*N)
    visited.append(2*N)
    
count = 0

while queue:
    ln = len(queue)
    count += 1
    for _ in range(ln):
        tmp = queue.popleft()
        if tmp == K:
            print(count)
            sys.exit()
        if tmp + 1 <= 100000 and tmp + 1 not in visited:
            queue.append(tmp+1)
            visited.append(tmp+1)
        if tmp - 1 >= 0 and tmp - 1 not in visited:
            queue.append(tmp-1)
            visited.append(tmp-1)
        if 2*tmp <= 100000 and 2*tmp not in visited:
            queue.append(2*tmp)
            visited.append(2*tmp)

コードは非常に乱雑です.解きほぐしたくないようだ.

リビジョン前のコード1の違いは、visted配列を使用して探索された点をQueueに再配置することなく、最大範囲10000が設定されていることである.

しかし、「inoptosed」コードのため、毎回ますます長いアクセスシーケンスを探索し、時間の複雑さが非常に高く、タイムアウトを招く.

✔修正後コード

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
MAX = 10 ** 5
dist = [0] * (MAX+1)

queue = deque([N])
while queue:
    x = queue.popleft()
    if x == K:
        print(dist[x])
        break
    for nx in (x-1, x+1, 2*x): #위처럼 if문으로 나누기보다, for문을 이렇게 활용하면 코드가 깔끔하다.
        if 0<= nx <= MAX and not dist[nx]:
            dist[nx] = dist[x] + 1  # Dynamic Programming의 처리와 유사하다.
            queue.append(nx)

は本当はもう少し考えるべきだったのですが、どうしたらいいか分からず、思わずグーグルのチャンスを使いました.
https://wook-2124.tistory.com/273

この問題を通じて、以下に示すように、私の誤った習慣を見つけることができます.

配列のナビゲーションによってタイムアウトを回避するためには、上記のdist配列のようにクエリで値を解放する必要があります.これは、アクセスの有無だけでなく、必要な時間も計算できるため、より効果的な方法です.

10000と同じ値を毎回使用するよりも、MAXと同じ変数にコードを記述するほうがきれいになります.

N=Kという特殊な場合は、漏らさないように一度に処理する方法を考えましょう.

必ずこの問題を通して学んだ知識を後の解答に応用しなければならない.
✔関連概念

メモリオーバーフロー防止およびタイムアウト