[Algorithm] DFS & BFS

DFS

📢 Depth First Search , 그래프의 모든 Node를 확인하는 방법 중 하나

---

🔎 DFS 특징

• 현재 Node의 모든 Edge들을 하나씩 확인해요.
• 더 이상 방문하지 않은 Edge가 없다면 이전 Node로 돌아가요.
• 재귀 호출 로 구현할 수 있어요.
• 인접 리스트에 구현하는 경우 시간 복잡도는 O(V + E), 인접 행렬에 구현하는 경우 시간 복잡도는 O(N^2)예요.

---

✒️ DFS 탐색 방법

1. 시작 Node를 기준으로 방문하지 않은 가장 왼쪽 Node 를 탐색하기 시작해요.
2. 탐색 중인 Node가 Leaf-Node가 아니라면 현재 Node를 기준으로 1번을 반복해요.
3. 탐색 중인 Node가 Leaf-Node라면 탐색을 마치고 Parent로 돌아가서 1번을 해요.
4. 모든 Node를 방문했다면 종료해요.

위의 그림은 DFS로 해당 Graph를 방문했을 때의 순서를 Node에 적어놨어요. 참고해주세요 ^^

---

📋 기본적인 DFS 구현 코드

Graph를 구현하는 코드는 상황에 따라 달라질 수 있어요. 여기서는 인접 리스트에 Graph를 구현했다고 가정하고 코드를 작성했어요.

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;

// 인접 리스트에 그래프 구현
vector<vector<int>> graph;
// 방문 여부 저장하는 배열
vector<bool> visited;

// 방문 여부 확인하는 함수
bool isVisited(int here) { return visited[here]; }

void dfs(int here) {
    cout << "Here is " << here << endl;
    for(int i = 0; i < graph[here].size(); i++) {
        int next = graph[here][i];
        // 아직 방문하지 않은 Edge가 있으면 방문해라
        if(not isVisited(next)) dfs(next);
    }
}

// Tree라면 상관없지만 끊겨있는 Graph라면 모든 정점을 방문하기 위해 필요한 코드
void dfsAll() {
    for(int i = 0; i < graph.size(); i++) {
        if(not isVisited(i)) dfs(i);
    }
}

---

📋 예제

백준 10026 - 적록색약

백준 10026 - 해답

백준 1987 - 알파벳

백준 1987 - 해답

---

BFS

📢 Breadth First Search, 그래프의 모든 Node를 확인하는 방법 중 하나

---

🔎 BFS 특징

• 시작 Node에서 가까운 Node부터 순서대로 탐색하는 알고리즘이에요.
• 방문한 Node의 인접한 Node들을 기억하고 있어야 해요.
• Queue 를 이용해 구현해요.
• BFS의 시간 복잡도 또한 DFS의 시간 복잡도와 같아요.

---

✒️ BFS 탐색 방법

위의 그림은 해당 Graph를 BFS로 탐색했을 때 방문하는 순서와 각 Node 이름을 알파벳으로 Node에 적어놨어요. 예를 들어 (A, 1)은 "Node 이름 A, 방문 순서 1번째" 라는 의미예요.

아래의 Queue 이미지는

• A번 Node를 기준으로 B, C가 Child-Node이므로 각각을 Queue에 넣었어요.
• A Node 다음으로는 Queue에 의해 B Node를 방문해요.
• B의 Child-Node로는 D, F가 있는데 Queue에 Push할 예정이니 점선으로 표시했어요.
  를 의미해요.

아래는 BFS 탐색 방법이에요.

1. 시작 Node를 기준으로 Child-Node들을 Queue에 Push 해요.
2. Queue에서 Node를 하나 Pop 하여 해당 노드를 탐색해요.
3. 2번에서 Pop한 Node를 기준으로 다시 Child-Node들을 Queue에 Push해요.
4. 1 ~ 3번을 반복해요.
5. 모든 Node를 탐색하면 종료해요.

---

📋 기본적인 BFS 구현 코드

여기서도 Graph는 인접 리스트로 구현이 되었다는 가정하에 코드르 작성했어요.

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

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::queue;

// 2차원 배열에 그래프 구현
vector<vector<int>> graph;

vector<int> bfs(int start) {
    // 방문 여부 저장하는 배열
    vector<bool> visited(graph.size(), false);
    // 다음 방문 할 Node 저장하는 Queue
    queue<int> nextNode;
    // 방문 순서 저장
    vector<int> order;
    visited[start] = true;
    nextNode.push(start);
    // Queue의 Node가 없다면 모든 Node를 방문했다고 볼 수 있다.
    while(not nextNode.empty()) {
        int here = nextNode.front();
        nextNode.pop();
        // 현재 Node의 모든 인접 Node들을 방문한다.
        for(int i = 0; i < graph[here].size(); i++) {
            int there = graph[here][i];
            // 다음 방문할 노드를 Queue에 넣는다.
            if(not visited[there])  {
                nextNode.push(there);
                visited[there] = true;
            }
        }
    }
    return order;
}

---

⏰ 시간 복잡도

DFS, BFS 둘 다 어떤 자료구조를 이용해 구현을 했는지에 따라서 달라져요.
N을 Node 개수, E를 Edge 개수라고 할게요.

인접 행렬

• DFS, BFS를 한 번 수행할 때 N번 반복문을 수행해요.

인접 리스트

---

📋 예제

백준 7569 - 토마토

백준 7569 - 해답

백준 2206 - 벽 부수고 이동하기

백준 2206 - 해답