[자료구조] DFS와 BFS

DFS 와 BFS란?

• DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘
• 그래프의 모든 노드를 탐색하는 방법임
• 두 알고리즘은 탐색의 순서와 방식에서 차이 있음
• 시간복잡도는 DFS/ BFS 동일함
  • -> 왜냐? 모든 조건 내 모든 노드를 검색하니까
  • --> But, 최단거리 구할 때는 BFS가 유리함

 

---

1. DFS (Depth-First Search)

- 개념: 

• DFS는 깊이 우선 탐색
• 한 노드에서 시작하여 다음 분기로 넘어가기 전에!!
• 해당 분기를 따라 최대한 깊이 내려가며 탐색하는 방법

 

- 특징: 

• 스택 (Stack) 사용
• 재귀 호출을 사용할 수 있음
• 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색

 

2. BFS (Breadth-First Search)

- 개념:

• BFS는 너비 우선 탐색
• 노드에서 시작하여 인접한 모든 노드 먼저 탐색
• 이후 각 인접 노드에 대해 다시 인접한 노드들을 탐색하는 방식

 

-특징: 

• 큐 (Queue)  사용
• 현재 노드의 모든 인접 노드들 탐색 후, 다음 인접 노드로 넘어감

#include <iostream>
#include <vector>
using namespace std;

/* 
함수: DFS 
매개변수: 2차원벡터 그래프, 방문 상태 표시하는 벡터, 현재 노드
*/
void DFS(vector<vector<int>> &Graph, vector<bool> &Visited, int Node) 
{
    Visited[Node] = true; // 현재 노드 방문했다고 표시
    cout << Node << " "; 
    
    // 현재 노드에 연결된 모든 노드 확인
    for (int i = 0; i < Graph[Node].size(); ++i) 
    {
        int Next = Graph[Node][i]; // 다음 방문할 노드
        
        if (!Visited[Next]) //만약 다음 노드 방문하지 않았다면
        {
            DFS(Graph, Visited, Next); // 다음 노드에 대해 DFS 재귀 호출
        }
    }
}

int main() 
{
    int NumNodes = 4; // 그래프의 노드 수를 정의
    
    vector<vector<int>> Graph(NumNodes); // 그래프를 인접 리스트 형태로 초기화

    Graph[0] = {1, 2}; // 그래프의 인접 리스트 정의
    Graph[1] = {0, 2};
    Graph[2] = {0, 1, 3};
    Graph[3] = {2};
    
    vector<bool> Visited(NumNodes, false); // 노드의 방문 상태를 저장하는 벡터 초기화

    cout << "DFS starting from node 0: "; // DFS 탐색 시작 노드를 출력

    DFS(Graph, Visited, 0);     // 노드 0부터 DFS 탐색 시작
    cout << endl;

    return 0;
}

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
함수 : BFS 너비우선탐색
매개변수 : 그래프의 인접 리스트, 방문 여부 저장 벡터, 시작 노드
*/
void BFS(vector<vector<int>>& Graph, vector<bool>& Visited, int Start) 
{
    queue<int> Q;
    Visited[Start] = true;
    Q.push(Start); // 시작 노드, 큐에 추가

    while (!Q.empty())  // 큐가 비어있지 않는 동안 반복
    {
        int Node = Q.front(); // 큐 앞에 있는 노드 가져옴
        Q.pop();			  // 큐 앞에 있는 노드 Pop
        cout << Node << " ";

        for (int i = 0; i < Graph[Node].size(); ++i)  // 현재 노드에 연결된 모든 노드 확인
        {
            int Next = Graph[Node][i];
            if (!Visited[Next]) // 다음 노드 방문X라면
            {
                Visited[Next] = true; // 다음 노드 방문했다고 표시
                Q.push(Next); // 다음 노드 큐에 추가
            }
        }
    }
}

int main() 
{
    int NumNodes = 4;
    
    vector<vector<int>> Graph(NumNodes);
    Graph[0] = {1, 2};
    Graph[1] = {0, 2};
    Graph[2] = {0, 1, 3};
    Graph[3] = {2};

    vector<bool> Visited(NumNodes, false);
    

    cout << "BFS starting from node 0: ";
    
    BFS(Graph, Visited, 0);
    
    cout << endl;

    return 0;
}

---

3. 참고 개념

3.1. 스택

-개념:

• LIFO (Last In, First Out) 구조
• 마지막에 삽입된 데이터가 가장 먼저 꺼내지는 방식
• 예시) 접시 쌓기 ->가장 나중에 올려놓은 접시를 가장 먼저 꺼냄

 

-스택의 주요 연산:

• push: 스택 맨 위에 데이터를 추가
• pop: 스택 맨 위에 있는 데이터를 제거하고 반환
• top : 스택의 맨 위에 있는 데이터를 제거하지 않고 반환
• isEmpty: 스택 비어 있는지 확인

 

3.2. 큐 (Queue)

-개념: 

• 큐는 FIFO (First In, First Out) 구조
• 먼저 삽입된 데이터가 먼저 꺼내지는 방식
• 예시) 줄 서기-> 먼저 줄을 선 사람이 먼저 서비스를 받음

 

-큐의 주요 연산:

• enqueue (or push): 큐의 뒤에 데이터를 추가
• dequeue (or pop): 큐의 앞에 있는 데이터를 제거하고 반환
• front: 큐의 앞에 있는 데이터를 제거하지 않고 반환
• isEmpty: 큐가 비어 있는지 확인

 

3.3. 재귀함수

-개념 : 

• 자기 자신을 호출하는 방식으로 문제를 해결하는 프로그래밍 기법
• 재귀는 주로 복잡한 문제를 더 작은 부분 문제로 나누어 해결할 때 사용

 

- 재귀 함수의 구성 2가지:

1. 기저 조건 (Base case):
   • 재귀 호출을 멈추는 조건
   • Base Case를 만족하면 함수는 더 이상 자기 자신을 호출하지 않고 종료
2. 재귀 호출 (Recursive call):
   • 함수가 자기 자신을 호출하여 문제를 더 작은 부분으로 나누어 해결

 

-참고 : 

• 재귀함수에서 기저조건이 없으면 스택오버플로우 발생
• 스택오버플로우는 callStack의 한계를 초과할 때 발생하는 런타임 오류

 

예시) 팩토리얼 계산

#include <iostream>
using namespace std;

int Factorial(int Num) 
{
    if (Num == 0)  // 기저 조건
        return 1;
    else 
        return n * factorial(n - 1);
}

int main() 
{
    int Number;

	cout << "Enter a positive integer: ";
    cin >> Number;

    cout << "Factorial of " << Number << " is " << Factorial(Number) << endl;

    return 0;
}

---

4.  개념 이해하기 쉽게 정리한 블로그 링크 :

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90