BFS와 DFS의 기초 개념 -3

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.

(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 

2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -2

지난 포스팅에서 각 정점들의 연결정보를 1) 인접행렬과 2) 연결 리스트에 저장하는 방법을 살펴보았습니다. 이번 포스팅에서는 이를 토대로 직접 DFS와 BFS를 구현해보겠습니다. 

1. 깊이우선탐색 (DFS)

깊이우선탐색은 스택 혹은 재귀호출을 통해 그래프를 순회하는 방법입니다.

깊이우선탐색은 우선 나(현재 노드)를 먼저 방문하고 나와 연결된 다른 놈들 중 하나를 방문하는 것입니다.

(단, 방문했던 노드는 방문하지 않는다.)

다음과 같은 정점과 간선이 있을 때, DFS 했을 경우의 결과를 미리 예상해보시기 바랍니다.

(단, 탐색의 시작은 1번 노드부터 시작하고 숫자가 작을수록 우선순위가 높다고 가정합니다.)

정답은 :

1 → 2 → 7 → 8 → 9 → 3 → 5 → 4 → 6

1) 1번 노드와 인접한 노드 2번, 3번, 4번 노드 중에 한 노드를 먼저 탐색한다. 

(낮은 숫자가 우선순위가 높기 때문에 2번 노드를 먼저 방문한다.)

2) 2번 노드와 인접한 1번, 7번 노드 중에 한 노드를 먼저 탐색한다. 하지만 1번 노드는 이미 방문했으므로

다시 방문하지 않고 7번 노드를 방문한다.

3) 1)과 2)를 반복한다.

위와 같은 내용은 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1에 설명되어 있으므로 참고바랍니다.

그럼 위의 설명을 토대로 직접 코드레벨에서 확인해보겠습니다.

dfs 함수는 자기 자신 내에서 또 다시 dfs함수를 호출하는 재귀함수 형태입니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAX 1001
 
vector<int> graph[MAX];
bool visited[MAX];
int n, m, v;
 
void dfs(int v) {
 
    cout << v << " ";
    visited[v] = true;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int x = graph[v][i];
        if (!visited[x]) {
            dfs(x);
        }
    }
 
}
 
 
int main(void) {
 
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++) {
        int num1, num2;
        cin >> num1 >> num2;
        graph[num1].push_back(num2);
        graph[num2].push_back(num1);
    }
 
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
 
    dfs(v);
    cout << endl;
 
    return 0;
}

2. 너비우선탐색 (BFS)

너비우선탐색은 Queue를 이용하여 그래프를 순회하는 방법입니다.

너비우선탐색은 해당 노드와 인접한 노드들 중 하나만을 선택하여 탐색을 진행하는 깊이우선탐색과는 달리

인접한 모든 노드들을 동시에(?) 방문하며 탐색을 진행한다고 생각하면 됩니다.

다음과 같은 정점과 간선이 있을 때, BFS 했을 경우의 결과를 미리 예상해보시기 바랍니다.

(단, 탐색의 시작은 1번 노드부터 시작하고 숫자가 작을수록 우선순위가 높다고 가정합니다.)

정답은 :

1 → 2 → 3 → 4 → 7 → 5 → 6 → 8 → 9

1) 1번 노드와 인접한 노드 2번, 3번, 4번 노드 모두를 탐색한다.

2) 2번 노드와 인접한 7번, 3번 노드와 인접한 5번, 4번 노드와 인접한 6번 노드를 방문한다. 

(1번 노드는 이미 방문했으므로 다시 방문하지 않는다.)

3) 1)과 2)를 반복한다.

위와 같은 내용은 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1에 설명되어 있으므로 참고바랍니다.

그럼 위의 설명을 토대로 직접 코드레벨에서 확인해보겠습니다.

bfs함수는 해당 노드와 인접한 모든 노드들을 Queue에 넣고 탐색을 진행하는 방식입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAX 1001
 
vector<int> graph[MAX];
bool visited[MAX];
int n, m, v;
 
 
void bfs(int v) {
 
    queue<int> q;
    q.push(v);
    visited[v] = 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]) {
                visited[y] = true;
                q.push(y);
            }
        }
 
    }
 
}
 
int main(void) {
 
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++) {
        int num1, num2;
        cin >> num1 >> num2;
        graph[num1].push_back(num2);
        graph[num2].push_back(num1);
    }
 
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
    bfs(v);
 
    return 0;
}

이상으로 BFS와 DFS의 개념설명에 대해 모두 마칩니다.

[알고리즘 문제 → BOJ] 카테고리에서 BFS와 DFS 기초문제부터 꾸준히 다룰 예정입니다.

이 포스팅을 통해 이해가 잘 되지 않으시는 분들은 쉬운 문제부터 차근차근 해결해보시기 바랍니다.

2019/02/10 - [알고리즘 문제/백준(BOJ)] - [백준 1260번] DFS와 BFS

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2178번] 미로탐색

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 7576번] 토마토

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2667번] 단지번호붙이기

2019/02/12 - [알고리즘 문제/백준(BOJ)] - [백준 2234번] 성곽 (Java, C++)