🔎 データ構造の基礎

ナビゲーションは、大量のデータから必要なデータを検索するプロセスです.
データ構造とは、「データを表示、管理、処理するための構造」である.
特に、スタックとキューはデータ構造の基礎概念であり、次の2つの重要な関数から構成されています.
挿入

(プッシュ):挿入データ

削除

(Pop):削除データ

また,オーバーフローと底流も考慮する.

📍 スタック

スタックは積み重ね箱にたとえることができます
下から上まで積み重ねて、下の箱を片付けるには、上の箱を置かなければなりません.
このような構造を先入後出構造、後入先出構造と呼ぶ
Pythonでスタックを使用する場合は、個別のライブラリを使用する必要はありません.
デフォルトリストのappend()メソッドとpop()メソッドを使用できます.
append()メソッドはリストの一番後ろにデータを挿入し,pop()メソッドはリストの一番後ろからデータを取り出す

📍 キュー

キューはキューにたとえることができます
後の人ほど、後の人ほど、「公正」な資料構造になる.
この構造を先入先出構造と呼ぶ
Pythonキューを実装する場合は、Collectionsモジュールが提供するDequeデータ構造を使用します.
dequeはスタックとキューを同時に持つ利点があります(リストデータよりもデータの挿入と削除が効率的で、キューライブラリを使用するよりも簡単です).
注:dequeオブジェクトをリストデータ型に変更する場合はlist()メソッドを使用します.

📍 さいきかんすう

DBSとBFSを実装するには、再帰関数も理解する必要があります.
再帰関数とは、自分の関数を再呼び出しすることです.
問題解決で再帰関数を使用する場合は、再帰関数がいつ終了するか、終了条件を明確にする必要があります.
(無限に関数を呼び出すことができるため)
再帰関数は内部でスタック資料構造と同じである
  => スタックデータ構造を使用する必要がある多くのアルゴリズムは、再帰関数によって容易に実現できる(exDFS)
再帰関数を使用する典型的な例は、ファクトリの問題です.
再帰関数は、数学の点化(再帰)をソースコードに直接移行し、重複文を使用するよりも簡潔な形式です.

🔎 グラフィックの基本構造

図形は「ノード」(Node)と「幹線」(Edge)で表され、ノードは「頂点」(Vertex)とも呼ばれます.
グラフィックナビゲーションは、1つのノードから複数のノードにアクセスします.
2つのノードが幹線で接続されている場合は、「2つのノードが隣接している」ことを示します.
グラフィックには2つの主な表現があります.

隣接行列:

グラフィックの2次元配列接続関係を表す

隣接リスト:グラフィックの接続関係をリストで表す方法

📍 隣接マトリクスは、2 D配列の各ノードの接続形式を記録します.
Pythonでは、2 Dリストで実現できます
接続されていないノード間で無限のコストを作成
隣接行列の例

INF = 999999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

# 결과
# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

📍 隣接リスト方式は、すべてのノードに接続されているノードに関する情報を格納する.
隣接リストを使用してグラフィックを表す場合は、2 Dリストを使用するだけです.
隣接リストの例

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

# 결과
# [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

二つの方式の違い

メモリ側面
-隣接マトリクス:すべての関係を格納するノードが多いほど、メモリが無駄になります.
-隣接リスト:

メモリ使用率が高く、関連情報のみを格納

速度側
-隣接マトリクス:2つの特定のノードが接続されているかどうかの情報をすばやく取得します.
-隣接リスト法:接続するデータを1つずつチェックする必要があるため、速度は

遅い.

🔎 DFS

DFSはDepth First Search、深度優先探索とも呼ばれ、グラフィックにおける深度優先のアルゴリズムである
DFSはスタック構造を採用し、具体的な操作過程は以下の通りである.
  1.ナビゲーション開始ノードをスタックに挿入してアクセス処理を行う
  2.スタックの最上位ノードにアクセスされていない隣接ノードがある場合は、スタックに配置します.
     アクセスされています.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
  3.2番目の処理を続行できなくなるまで繰り返す

🔎 BFS

BFSは、先頭から探索を開始し、幅を優先して探索するアルゴリズムであり、簡単に言えば、隣接ノードから探索を開始するアルゴリズムである.
BFS実装では、通常、先入先出のキューリソース構造が採用される.
DFSは可能な限り遠いノードを優先的にブラウズするが,BFSは逆である.
通常、BFSの実際の実行時間はDFSよりも優れている
BFSはキューリソース構造を使用し、具体的な操作過程は以下の通りである.
  1.ナビゲーション開始ノードをキューに挿入してアクセス処理する
  2.キューからノードを取り出し、そのノードの隣接ノードの未アクセスノードを
     すべてキューを挿入してアクセス
  3.2番目の処理を続行できなくなるまで繰り返す

📝 整理する

DFSSBFS動作原理スタックキューの実現方法再帰関数を用いたキューデータ構造

▼▼実戦問題

📝 冷たい飲み物

N x Mサイズのアイスフレームがございます
0は穴、1は仕切り板の存在を示す
穴の上、下、左、右の間の接続
所定の氷棚の形状で生成されるアイスクリームの総数を求めるプログラムを作成してください.

入力条件
−第1行は、氷フレームの長手方向長さN及び横方向長さM(1≦N,M≦1000)を与える
-2列目からN+1列目まで氷棚の形状を形成する
-この時点で穿孔された部分は0であり、そうでない部分は1

である.

出力条件
-一度に作れるアイスクリームの量を出力

問題の説明

DFSで解決可能
1.ある場所の周囲の上下、左、右を表示します.周囲の場所の値が「0」の場合、まだ訪問していない場所がある場合は、その場所を訪問してください.
2.アクセスポイントで上、下、左、右を再表示し、すべての接続ポイントにアクセスできます.
3.1～2回のプロセスをすべてのノードに繰り返し、アクセスされていないポイントの数を計算する

ソースコード

📝 迷宮を脱出する

主人公はN x Mサイズの矩形迷宮に閉じ込められている.
迷宮には何匹かの怪物がいて、私たちはそれを脱出しなければなりません.
主人公の位置は(1,1),迷路の出口は(N,M)の位置にあり,一度に1つの格子を移動できる.
このときモンスターがいる部分は0、モンスターがいない部分は1
迷宮は必ず逃げられる形で現れる
主人公が逃げるために移動しなければならない最小格数を求める.
(開始セルと最後のセルを含むセルの計算)

入力条件
−1行目に2つの整数N、M(4≦N、M≦200)がある.
  次のN行では、各行に迷路の情報としてM個の整数(0または1)がある.
  各数値はスペースで表示され、最初と最後のセルは常に1です.

出力条件
-最初の行に最小移動格子数を出力

問題の説明

BFSを使用する場合、非常に効果的に問題を解決することができます
BFSは,始点に近いノードから順にグラフィック内のすべてのノードをナビゲートするためである.
(1,1)1点からBFSを実行し,すべてのノードの値を距離情報として挿入すればよい.
ノードにアクセスすると、リストの値は前のノードの距離に1を加算します.

ソースコード

📒 これがコードテストです教材で学習した内容を整理した.