[알고리즘] DFS & BFS 알고리즘

1. DFS (Depth-First Search)

1) DFS의 정의

• 깊이 우선 탐색이라고 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택(Stack) 자료구조 또는 재귀함수를 이용
• 동작 과정
  a. 탐색 시작 노드를 스택에 삽입하고 방문 처리
b. 스택 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드 없으면 스택에서 최상단 노드 꺼냄
c. 더 이상 2번 과정 수행할 수 없을 때까지 반복

2) DFS 동작 예시(방문 기준 : 번호가 낮은 인접 노드부터)
a. 시작 노드를 1로 하여 탐색을 시작한다.

b. 최상단 노드인 1에 인접하고 방문하지 않은 노드로 2, 3, 8이 존재한다.
이 중에 번호가 낮은 2를 최상단 노드로 스택에 삽입하고 방문 처리한다.

c. 최상단 노드인 2에 인접하고 방문하지 않은 노드로 7이 존재한다.
따라서 7을 최상단 노드로 스택에 삽입하고 방문 처리한다.

d. 최상단 노드인 7에 인접하고 방문하지 않은 노드로 6, 8이 존재한다.
이 중에 번호가 낮은 6을 최상단 노드로 스택에 삽입하고 방문 처리한다.

e. 최상단 노드인 6에 인접하고 방문하지 않은 노드가 없으므로 6을 스택에서 삭제한다.

f. 6이 삭제되어 다시 최상단 노드가 된 7에 인접하고 방문하지 않은 노드로 8이 존재한다.
따라서 8번 노드를 최상단 노드로 스택에 삽입하고 방문 처리한다.

e. 이와 같은 방법으로 계속 진행했을 때 전체 노드의 탐색 순서는 아래와 같다.
: 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

3) DFS 예제 코드

#include <bits/stdc++.h> // 자주 쓸만한 헤더파일을 전부 include 하는 헤더파일

using namespace std;

bool visited[9];	// 각 노드 방문 여부 저장하는 bool 변수 배열
vector<int> graph[9];	// 한 노드에 인접한 노드들을 저장하는 vector들의 배열로 그래프 구현

void DFS(int x)
{
    // 현재 노드를 방문 처리
    visited[x] = true;
    cout << x << ' ';
    
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for (int i = 0; i < graph[x].size(); i++)
    {
        int y = graph[x][i];
        if (!visited[y])    // 방문하지 않은 노드에 대해서 재귀적으로 DFS 함수 실행
            DFS(y);
    }
}

int main()
{
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(2);	// vector.push_back(data) : vector 맨 뒤에 data라는 원소 추가
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장
    graph[8].push_back(1);
    graph[8].push_back(7);

    DFS(1);
}

2. BFS(Breadth-First Search)

1) BFS의 정의

• 너비 우선 탐색이라고 불리며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐(Queue) 자료구조를 이용
• 동작과정
  a. 탐색 시작 노드를 큐에 삽입하고 방문 처리
b. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
c. 더 이상 2번의 과정 수행할 수 없을 때까지 반복

2) BFS 동작 예시(방문 기준 : 번호가 낮은 인접 노드부터)

a. 시작 노드를 1로 하여 탐색을 시작한다.

b. 최상단 노드인 1을 꺼내고, 방문하지 않은 인접 노드인 2, 3, 8을 차례로 큐에 삽입하고 방문 처리한다.

c. 최상단 노드인 2를 꺼내고, 방문하지 않은 인접 노드인 7을 큐에 삽입하고 방문 처리한다.

d. 최상단 노드인 3을 꺼내고, 방문하지 않은 인접 노드인 4, 5를 큐에 삽입하고 방문 처리한다.

e. 최상단 노드인 8을 꺼내고, 방문하지 않은 인접 노드가 없으므로 무시한다.

f. 최상단 노드인 7을 꺼내고, 방문하지 않은 인접 노드인 6을 큐에 삽입하고 방문 처리한다.

e. 이와 같은 방법으로 계속 진행했을 때 전체 노드의 탐색 순서는 아래와 같다.
: 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

3) BFS 예제 코드

#include <bits/stdc++.h> // 자주 쓸만한 헤더파일을 전부 include 하는 헤더파일

using namespace std;

bool visited[9]; // 각 노드 방문 여부 저장하는 bool 변수 배열
vector<int> graph[9];   // 한 노드에 인접한 노드들을 저장하는 vector들의 배열로 그래프 구현


void BFS(int start)
{
    queue<int> q;   // 노드들을 저장할 큐 선언

    // 시작 노드를 큐에 삽입하고 방문 처리'
    q.push(start);
    visited[start] = true;

    while (!q.empty())      // 모든 노드 방문하여 큐가 빌 때까지
    {
        // 최상단 노드 지정 및 삭제
        int x = q.front();  
        q.pop();
        cout << x << ' ';

        for (int i = 0; i < graph[x].size(); i++)   // 최상단 노드에 인접한 모든 노드들에 접근
        {
            int y = graph[x][i];    
            if (!visited[y])    // 방문하지 않은 인접 노드에 대해 큐에 삽입 및 방문 처리
            {
                q.push(y);
                visited[y] = true;
            } 
        }
    }
}

int main()
{
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장
    graph[8].push_back(1);
    graph[8].push_back(7);

    BFS(1);
}

출처 : 유튜브 동빈나(https://youtu.be/7C9RgOcvkvo)