📌 알고리즘 - DFS 개념

깊이 우선 탐색이란?

깊이 우선 탐색이란 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다.

• 넓게 탐색하는 BFS와 달리 DFS는 깊게 탐색한다.
• 모든 노드를 방문하고 싶을 때 이 알고리즘을 사용한다.
• 단순 검색 속도 자체는 BFS에 비해서 느리다.

깊이 우선 탐색 구현 방법

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

깊이 우선 탐색의 특징

• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

깊이 우선 탐색의 시간 복잡도

인접 리스트로 표현된 그래프: $O(N+E)$
인접 행렬로 표현된 그래프: $O(N^2)$
그래프 내에 적은 숫자의 간선을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

깊이 우선 탐색의 구현

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[502][502];
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
    stack<pair<int,int>> S;
    vis[0][0] = 1; // 시작 정점 방문 처리
    S.push({0,0}); // 스택에 push
    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];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 보드를 벗어나면 continue
            if (vis[nx][ny]) continue; // 이미 방문한 정점이면 continue
            vis[nx][ny] = 1; // 방문 처리
            S.push({nx,ny}); // 스택에 push
        }
    }      
}