[알고리즘 공부] 실전 알고리즘 10강-DFS

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

알고리즘 설명

DFS (Depth First Search) : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

DFS 알고리즘에서는 좌표를 담을 stack이 필요하다.

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

pair는 두 원소를 묶어서 다닐 수 있는 STL로 이 pair는 미리 대소 관계가 설정되어 있다.
알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교한다.
DFS를 구현할 때 스택에 좌표를 넣어야하는데 이때 pair를 사용한다.

---

구현

#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

BFS와 DFS는 방문순서에 큰 차이가 있다. BFS의 인접한 원소는 현재 원소보다 1만큼 떨어져 있다는 성질이 DFS에는 성립하지 않는다. DFS는 일단 한방향으로 막히기 전까지 직진하는 성질이 있는데 이 성질때문에 거리를 구하는 문제에서는 DFS를 사용할 수 없다.

Flood Fill은 BFS DFS 둘 다 사용가능하지만 거리측정은 BFS만 가능하다.
그래서 다차원 배열에서 순회하는 문제는 BFS로 다 해결할 수 있다.
DFS는 그래프와 트리 자료구조를 배울때 필요하다.