[ドッキングステーションの実戦アルゴリズム]DFS,深さ優先ナビゲーション
16202 ワード
DFS(Depth First Search)多次元配列で各セルにアクセスする際の優先アクセス深度のアルゴリズム 開始セルをスタックに入れ、アクセスタグ を残します.スタックから要素を取り出し、そのセルの上下左右に隣接するセルに対して を3回行う.以前にセルにアクセスした場合は、何も行われません.セルに初めてアクセスした場合は、「アクセス済」というタグが残り、スタック にセルが挿入されます.スタックが空きになるまで2回繰り返します.
✔BFSとの違い:Q->スタック
インプリメンテーション
アクセス順が異なります. 距離を計算するには、DFSは使用できません. Flood fill両方可能です. 📍 グラフィックとツリーはDFSを使うので、コンセプトを知るだけ!
プロセス
✔BFSとの違い:Q->スタック
インプリメンテーション #include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int,int> > S;
vis[0][0] = 1; // (0, 0)을 방문했다고 명시
S.push({0,0}); // 스택에 시작점인 (0, 0)을 삽입.
while(!S.empty()){
pair<int,int> cur = S.top(); S.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
S.push({nx,ny});
}
}
}
BFS vs DFS
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int,int> > S;
vis[0][0] = 1; // (0, 0)을 방문했다고 명시
S.push({0,0}); // 스택에 시작점인 (0, 0)을 삽입.
while(!S.empty()){
pair<int,int> cur = S.top(); S.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
S.push({nx,ny});
}
}
}
Reference
この問題について([ドッキングステーションの実戦アルゴリズム]DFS,深さ優先ナビゲーション), 我々は、より多くの情報をここで見つけました https://velog.io/@jieun_han/바킹독의-실전-알고리즘-DFS-깊이-우선-탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol