Cha Cha's Blog
🌙
Algorithm

깊이 우선 탐색(DFS: Depth First Search)

정의

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색

특징

  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
  • 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것
  • 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택
  • 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
  • 단순 검색 속도는 너비 우선 탐색(BFS)에 비해서 느리다.
  • 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
  • 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
  • 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
    • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

시간복잡도

  • DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
    • 인접 리스트로 표현된 그래프: O(N+E)
    • 인접 행렬로 표현된 그래프: O(N^2)
  • 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

과정

notion image
  1. a 노드(시작 노드)를 방문한다.
    1. 방문한 노드는 방문했다고 표시한다.
  1. a와 인접한 노드들을 차례로 순회한다.
    1. a와 인접한 노드가 없다면 종료한다.
  1. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
    1. b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
  1. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
    1. 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
    2. 아직 방문이 안 된 정점이 없으면 종료한다.
    3. 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

구현

  1. 순환 호출 이용
DFS와 BFS
//1260-DFS와 BFS-Silver4-https://www.acmicpc.net/problem/1260

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define fastIo cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)

using namespace std;

int N, M, V;
int one, two;

vector<int> v[10001];

int dfsVisited[1001];
vector<int> dfsResult;

int bfsVisited[1001];
vector<int> bfsResult;

void dfs(int x) {
    //방문 기록
    dfsVisited[x] = 1;
    dfsResult.push_back(x);

    for (int i = 0; i < v[x].size(); ++i) {
        //방문 기록이 없으면
        if (!dfsVisited[v[x][i]] == 1) {
            //재귀
            dfs(v[x][i]);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);

    //초기 방문 기록
    bfsVisited[start] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        //결과 기록
        bfsResult.push_back(x);

        for (int i = 0; i < v[x].size(); ++i) {
            //방문 기록이 없으면
            if (!bfsVisited[v[x][i]] == 1) {
                q.push(v[x][i]);

                //방문 기록
                bfsVisited[v[x][i]] = 1;
            }
        }
    }
}

int main() {
    fastIo;

    //입력
    cin >> N >> M >> V;

    for (int i = 0; i < M; ++i) {
        cin >> one >> two;

        v[one].push_back(two);
        v[two].push_back(one);
    }

    //정렬
    for (int i = 1; i <= N; ++i) {
        sort(v[i].begin(), v[i].end());
    }

    //dfs
    dfs(V);

    //bfs
    bfs(V);

    //출력
    //dfs
    for (int i = 0; i < dfsResult.size(); ++i){
        cout << dfsResult[i] << " ";
    }

    //bfs
    cout << '\n';
    for (int i = 0; i < bfsResult.size(); ++i){
        cout << bfsResult[i] << " ";
    }
}
  1. 명시적인 스택 사용
    1. 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.
//1260-DFS와 BFS-Silver4-https://www.acmicpc.net/problem/1260

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

#define fastIo cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)

using namespace std;

int N, M, V;
int one, two;

vector<int> v[10001];

int dfsVisited[1001];
vector<int> dfsResult;
stack<int> dfsStack;

int bfsVisited[1001];
vector<int> bfsResult;

void dfs(int x) {
    //방문 기록
    dfsVisited[x] = 1;
    dfsResult.push_back(x);
    dfsStack.push(x);

    while (!dfsStack.empty()) {
        bool able = false;
        int t = dfsStack.top();

        for (int i = 0; i < v[t].size(); ++i) {
            //방문 기록이 없으면
            if (!dfsVisited[v[t][i]] == 1) {
                dfsResult.push_back(v[t][i]);
                dfsStack.push(v[t][i]);
                //방문 기록
                dfsVisited[v[t][i]] = 1;
                able = true;
                break;
            }
        }

        //이번에 한번도 방문하지 않으면
        if (!able) {
            dfsStack.pop();
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);

    //초기 방문 기록
    bfsVisited[start] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        //결과 기록
        bfsResult.push_back(x);

        for (int i = 0; i < v[x].size(); ++i) {
            //방문 기록이 없으면
            if (!bfsVisited[v[x][i]] == 1) {
                q.push(v[x][i]);

                //방문 기록
                bfsVisited[v[x][i]] = 1;
            }
        }
    }
}

int main() {
    fastIo;

    //입력
    cin >> N >> M >> V;

    for (int i = 0; i < M; ++i) {
        cin >> one >> two;

        v[one].push_back(two);
        v[two].push_back(one);
    }

    //정렬
    for (int i = 1; i <= N; ++i) {
        sort(v[i].begin(), v[i].end());
    }

    //dfs
    dfs(V);

    //bfs
    bfs(V);

    //출력
    //dfs
    for (int i = 0; i < dfsResult.size(); ++i){
        cout << dfsResult[i] << " ";
    }

    //bfs
    cout << '\n';
    for (int i = 0; i < bfsResult.size(); ++i){
        cout << bfsResult[i] << " ";
    }
}

비교군과의 차이

BFS

면접 질문

출처

[자료구조] 그래프(Graph)란