[プログラマーアルゴリズム]ゲームマップ最短距離

質問する

ゲームマップ最短距離

に近づく

問題の説明を読むと、探求問題であることがわかります.しかし,これは単純な探索ではなく,最短距離を求める探索であるため,dfsではなくbfsで解くことができる.始点から、上下左右を見るたびに、これまで見たことも壁でもない場所が見つかった場合は、キューに位置情報を含め、次の場所をブラウズし続けます.
探索したタグをcheck配列に配置して管理し、その位置にアクセスしてキューに入れるのではなくcheck値を発見したときに適用してこそ、効率スコアが得られます.訪問時にチェックすると、訪問前に何度も同じ場所をチェックしますから.こちらはよく説明されています.

コード#コード#

def solution(maps):
    n = len(maps)
    m = len(maps[0])

    #방문 여부 확인하는 배열
    check = [[False for i in range(m)] for j in range(n)]
    check[0][0]= True

    #bfs용 스택
    s=[]
    s.append((0,0,1)) #row,col,distance

    while s:
        current = s.pop(0)
        row = current[0]
        col = current[1]
        dist = current[2]


        #상대팀 진영 도착
        if row==n-1 and col==m-1:
            return dist
    
        nextRow = [row+1,row-1,row,row]
        nextCol = [col,col,col-1,col+1]
        
        for i in range(4):
            if nextRow[i]<0 or nextRow[i]>=n or nextCol[i]<0 or nextCol[i]>=m:
                continue
            elif check[nextRow[i]][nextCol[i]]==False and maps[nextRow[i]][nextCol[i]]==1:
                check[nextRow[i]][nextCol[i]] = True
                s.append((nextRow[i],nextCol[i],dist+1))
  
    return -1

改善された回答

上記のコードは、すべてのテスト例を通過することもできますが、効率を向上させるために、コードを改善しました.
Pythonでは,リストのpop演算には通常O(n)の時間的複雑さが必要である.したがって,リストの代わりに,両端値に近づくとO(1)時間の複雑さを持つdequeが用いられる.

from collections import deque
    

def solution(maps):
    n = len(maps)
    m = len(maps[0])

    #방문 여부 확인하는 배열
    check = [[False for i in range(m)] for j in range(n)]
    check[0][0]= True

    #bfs용 큐
    s=deque()
    s.appendleft((0,0,1)) #row,col,distance

    while s:
        current = s.pop()
        row = current[0]
        col = current[1]
        dist = current[2]


        #상대팀 진영 도착
        if row==n-1 and col==m-1:
            return dist
    
        nextRow = [row+1,row-1,row,row]
        nextCol = [col,col,col-1,col+1]
        
        for i in range(4):
            if nextRow[i]<0 or nextRow[i]>=n or nextCol[i]<0 or nextCol[i]>=m:
                continue
            elif check[nextRow[i]][nextCol[i]]==False and maps[nextRow[i]][nextCol[i]]==1:
                check[nextRow[i]][nextCol[i]] = True
                s.appendleft((nextRow[i],nextCol[i],dist+1))

        #print(s)
    
    return -1

リストを使用した結果

Dequeを使用した結果
あまり差はありませんが、dequeの速度が速いことが細かくわかります.

改善された解答2

check配列を単独で生成して管理するのはすでにアクセスした場所では効率的ではないので,checkのないチェック方法を考えた.どうせ地図は数字0と1で埋められていて、0は壁で、1は長さです.したがって,アクセスのたびにmapsの値に1を足すと,1ではなく0(壁を塞ぐ)か,すでにアクセスした場所が分かる.check配列の代わりにこの方法を用いることができる.

from collections import deque
    

def solution(maps):
    n = len(maps)
    m = len(maps[0])


    #bfs용 큐
    s=deque()
    s.appendleft((0,0,1)) #row,col,distance

    while s:
        current = s.pop()
        row = current[0]
        col = current[1]
        dist = current[2]


        #상대팀 진영 도착
        if row==n-1 and col==m-1:
            return dist
    
        nextRow = [row+1,row-1,row,row]
        nextCol = [col,col,col-1,col+1]
        
        for i in range(4):
            if nextRow[i]<0 or nextRow[i]>=n or nextCol[i]<0 or nextCol[i]>=m:
                continue
            elif maps[nextRow[i]][nextCol[i]]==1:
                maps[nextRow[i]][nextCol[i]]+=1
                s.appendleft((nextRow[i],nextCol[i],dist+1))
    
    return -1

print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1]]))
print(solution([[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]))
print(solution([[1,1,1],[1,1,1],[1,1,1]])

check配列を単独で生成することに比べて,時間は確かに減少した.