0x0A. DFS - 깊이 우선 탐색

0x0A DFS

0x00 알고리즘 설명

DFS (Depth First Search) : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘

0x01 예시 (Flood Fill)

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)

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});
    }
  }
}

0x02 BFS vs DFS

→ BFS는 큐를 쓰고 DFS는 스택을 쓴다. → BFS는 BFS의 성질인 거리 순으로 방문, DFS는 한 방향으로 막힐 때 까지 쭉 직진

→ 그리고 BFS에서 유용하게 썼던 " 현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다 " 는 성질이 DFS에서는 성립X 그래서 앞으로 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만

DFS는 나중에 그래프와 트리라는 자료구조를 배울 때 필요 아예 잊어버리지는 말고 DFS는 스택을 써서 다차원 배열의 순회를 처리하는 알고리즘이다, 깊이를 우선해서 탐색 기억하기.

리뷰

DFS는 BFS와 다른점이 있다는 것만 알고 넘어가서 가볍게 읽고 이해하고 넘어갔다.

DFS는 나중에 트리, 그래프에서 사용할 예정이니 잘 머리속에 간직해둬야겠다.

이번 단원은 가볍게 들을 수 있는 강의였다.

다음은 0X0B 재귀로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의