WEEK. 02 2022.04.08 TIL

ナビゲーションは、大量のデータの中で必要なデータを検索するプロセスです.典型的なグラフィックナビゲーションアルゴリズムはDFSとBFSを含む.

スタックデータ構造

最初に入力されるデータは、後で出力されるフォーマット(先に入力してから出力する)のデータ構造であり、入口と出口は同じ形式でスタックを可視化することができる.

キューデータ構造

まず入力したデータが先に出る形式(先入先出)の資料構造は,入口も出口も穴が開いたトンネルのような形式で可視化される.

ユークリッドアークほう

2つの自然数A,Bについて、(A>B)AをBで割った残りの数をRと呼ぶと、AとBの最大承諾数はBとRの最大公約数に等しい.

def uh(a, b): 
    print(a, b)
    if a%b == 0:
        print(b)
        return

    return uh(b, a%b)

DFS(Depth-First Search)

DFSは深さ優先ナビゲーションとも呼ばれ、グラフィックで深さを優先的に検索するアルゴリズム

である.

DFSでは、スタックデータ構造(または再帰関数)が使用されます.具体的な動作は次のとおりです.
1)ナビゲーション開始ノードをスタックに挿入してアクセス処理を行う.
2)隣接ノードがスタックの最上位ノードにアクセスしていない場合は、スタックに入れてアクセス処理を行います.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
3)この手順を2回まで繰り返します.

隣接するノードが複数ある可能性があるため、どのノードからアクセスを開始する必要があるかの基準は、問題によって異なる可能性があります.アクセス順序が関係なくても存在します.

graph = [[], # 각 노드들의 인접 노드 번호
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]]

visited = [False] * 9 # 예제에서 1번 노드부터 시작했기 때문에 0 index는 비워둠.

def dfs_prac(i, graph, visited):
    visited[i] = True # 현재 노드에 대해 방문 처리
    print(i, '번째 노드를 방문하였습니다.')
    for j in graph[i]: # 현재 노드들의 인접 노드들을 방문하기 위한 반복문
        if not visited[j]: # 인접 노드가 방문 처리가 안되어 있으면 해당 노드로 방문
            dfs_prac(j, graph, visited) #스택 자료구조의 용도로 재귀함수 사용

dfs_prac(1, graph, visited)

BFS(Breadth-First Search)

BFSは、幅優先ナビゲーションとも呼ばれ、特定の目的のための最短距離

である、グラフィック内のノードから優先ナビゲーションを開始するアルゴリズムexである.

BFSはキュー材料構造を採用し、具体的な操作は以下の通りである.
1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
2)ノードをキューから取り出し,そのノードのすべての隣接ノードにおいてアクセスされていないノードをキューに挿入し,アクセス処理を行う.
3)この手順を2回まで繰り返します.

def bfs_prac(i, graph, visited):
    queue = deque([i]) # 큐 생성하여 첫번째 탐색 노드 삽입
    visited[i] = True # 삽입한 노드 방문 체크

    while queue: # 큐의 노드가 모두 없어질때까지
        v = queue.popleft() # 큐에서 노드 하나를 뽑아 출력
        print(v, end=' ')
        for j in graph[v]: # 출력한 노드의 인접 노드들에 대해 탐색
            if not visited[j]: # 방문체크 확인
                queue.append(j) # 방문하지 않았으면 큐에 노드 삽입
                visited[j] = True # 해당 노드 방문체크

bfs_prac(1, graph, visited)

例-冷凍飲料

N xMの大きさの氷の棚の上で、穴がある部分は0で、仕切りがある部分は1で、

を表しています.

穴は上、下、左、右に接続されています

特定の場所の周囲の上、下、左、右を表示します.周囲の場所に0の値があるが、まだアクセスしていない場所がある場合は、その場所

にアクセスします.

でアクセスした場所で、上、下、左、右を再度表示し、アクセスプロセスを繰り返して、接続されているすべての場所にアクセスできます.

のすべてのノードを1～2回繰り返し、アクセスされていないポイントの数をカウントします.

# dfs로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
    # 맵의 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면 
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출하여 방문
        dfs(x-1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return True

    return False

n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 모든 노드(위치)에 대해 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 dfs 수행
        if dfs(i, j) == True:
            result += 1 # 순차적으로 탐색 시 이미 방문 처리가 되었다는 것은 다른 노드의 탐색으로 인해 이미 방문 처리가 되었음을 의미하므로 처음 방문하는 노드에서 dfs를 호출하여 탐색이 끝난 후 True를 반환하면 카운트 함.

print(result) # 정답 출력

迷宮から逃げる

NxMサイズの長方形迷路にモンスターが存在し、それを避けなければならない.モンスターがいる部分は0、モンスターがいない部分は1、表示は

東彬が逃げるために移動しなければならない最小格数.(最短距離ナビゲーション)
1)BFSは,始点に近いノードから順にグラフィック内のすべてのノードをブラウズする.
2)上,下,左,右に接続されたすべてのノードまでの距離は1である.そこで、(1,1)点からBFSを実行し、全てのノードの最短距離値を記録することで問題を解決する

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 좌표를 행, 열로 표현하다 보니 (0,0)에서 위로 올라갈 경우 -1행 즉 (-1, 0)이 되므로 이렇게 적용한듯
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    # 큐(Qeueu) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인. 그 후 괴물이 있거나(graph[nx][ny] == 0) 맵의 범위를 벗어나면 (가로=6, 세로=5) 중단. i = (0, 1, 2, 3) 각 값이 방향을 의미함.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1 # 출발하는 위치와 도착하는 위치를 포함하기 때문에 출발하는 경우 1로 표시되어 있으므로 새로운 방향으로 탐색 시 1을 더해준다.
                queue.append((nx, ny)) # 탐색을 위해 큐에 해당 위치를 삽입
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

-考えを整理する

バイナリナビゲーション

バイナリナビゲーション:ソートされたリストのナビゲーション範囲を半分縮小し、

を使用してデータをナビゲートします.

始点、終点、および中点を使用してナビゲーション範囲

を設定する.
Pythonバイナリナビゲーションライブラリ

対左(a,x):配列aにxを挿入する最も左側のインデックス

を返し、ソート順を維持します.

対右(a,x):配列aにxを挿入する最も右のインデックス

を返し、ソート順を維持します.

from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index
    
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

パラメトリックサーチ

最適化問題を決定問題(「はい」または「いいえ」)の解決方法に変換します.
ex)特定の条件を満たす最適値を迅速に見つける最適化問題

は、通常、符号化試験において、パラメータ探索問題をバイナリ探索によって解決することができる.

のナビゲーション範囲が広い場合は、バイナリナビゲーションを適用する必要があります.