[C++] DFS와 BFS 구현하기

 

1️⃣DFS : 깊이 우선 탐색 (Depth-First Search)

1. What? : 루트 노트에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
2. When use? : 모든 노드를 방문하고자 하는 경우 사용한다.
3. How? : 스택(Stack) or 재귀함수, 노드 방문 여부(isVisited[idx]) 이용

2️⃣BFS : 너비 우선 탐색 (Breadth-Frist Search)

1. What? : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
2. When use? : 두 노드 사이의 최단 경로 or 임의의 경로를 찾을 때 사용한다.
3. How? : 큐(Queue), 노드 방문 여부(isVisited[idx]) 이용

✔︎프림(Prim)과 다이스트라(Dijkstra) 알고리즘과 유사하다

⏳시간복잡도 (N: 노드, E: 간선)
1. 인접 리스트로 표현된 그래프 : O( N+E)
2. 인접 행렬로 표현된 그래프 : O(N^2)

---

[C++로 구현한 DFS]

재귀함수를 이용한 방법

스택을 이용한 방법

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int N, M, S;

vector<int> adjList[1001];
bool isVisited[1001] = {false,};
stack<int> st;

/* 재귀 함수를 이용한 dfs */
void dfs(int V) {
    if (isVisited[V]) { return; } // 이미 방문했다면 return
    isVisited[V] = true;
    printf("%d ", V);
    
    for (int i=0; i<adjList[V].size(); i++) { // 인접 노드 재귀함수 호출
        int next = adjList[V][i];
        dfs(next);
    }
}

/* stack을 이용한 dfs */
void dfs2(int V) {
    st.push(V); // 루트 노드 삽입
    
    while (!st.empty()) {
        int cur = st.top();
        st.pop();
        
        if (isVisited[cur]) { continue; }
        isVisited[cur] = true;
        
        printf("%d ", cur);
        
        // 숫자가 작은 노드 먼저 방문하기 위해 reverse
        for (int i=adjList[cur].size()-1; i>=0; i--) { 
            int next = adjList[cur][i];
            st.push(next);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &S); // 노드 수: N, 간선 수: M, 시작 노드: S
    
    for (int i=0; i<M; i++) {
        int s, e;
        scanf("%d %d", &s, &e);
        adjList[s].push_back(e);
        adjList[e].push_back(s);
    }
    
    // sort
    for (int i=0; i<1001; i++) {
        sort(adjList[i].begin(), adjList[i].end());
    }

	  fill_n(isVisited, 1001, false); // 방문 여부 초기화
	  dfs(S);  

    fill_n(isVisited, 1001, false); // 방문 여부 초기화
    dfs2(S);

    return 0;
}

 

[C++로 구현한 BFS]

Queue를 이용한 방법

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, S;

vector<int> adjList[1001];
bool isVisited[1001] = {false,};
queue<int> que;

void bfs(int V) {
    que.push(V); // 루트 노드 삽입
    
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        
        if (isVisited[cur]) { continue; }
        isVisited[cur] = true;
        
        printf("%d ", cur);
        
        for (int i=0; i<adjList[cur].size(); i++) { // 인접 노드들 삽입
            int next = adjList[cur][i];
            que.push(next);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &S);
    
    for (int i=0; i<M; i++) {
        int s, e;
        scanf("%d %d", &s, &e);
        adjList[s].push_back(e);
        adjList[e].push_back(s);
    }
    
    // sort
    for (int i=0; i<1001; i++) {
        sort(adjList[i].begin(), adjList[i].end());
    }
    
    fill_n(isVisited, 1001, false); // 방문 여부 초기화
    bfs(S);
    
    return 0;
}

---

📖DFS, BFS 문제
백준 1260 문제 : DFS와 BFS
[C++][백준 2178] 미로탐색 - BFS를 이용한 최단거리