[Computer Algorithms] DFS & BFS (DFS와 BFS)

DFS (Depth-First-Search, 깊이 우선 탐색)

루트 노드 혹은 임의 노드에서 다음 브렌치로 넘어가기 전에, 해당 브렌치를 모두 탐색하는 방법이다. 스택 또는 재귀호출로 구현할 수 있다.

 

- 스택을 사용한 DFS

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, M, S;
vector<int> graph[100];
vector<int> visited;
vector<int> result;

void input()
{
    cin >> N >> M >> S;
    visited.resize(N);
    fill(visited.begin(), visited.end(), 0);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs()
{
    stack<int> s;
    s.push(S);
    visited[S] = 1;

    while (!s.empty())
    {
        int cur = s.top();
        s.pop();

        result.push_back(cur);

        for (int next : graph[cur])
        {
            if (!visited[next])
            {
                s.push(next);
                visited[next] = 1;
            }
        }
    }
}

void output()
{
    for (int i : result)
        cout << i << " ";
    cout << endl;
}

int main(void)
{
    input();
    dfs();
    output();

    return 0;
}

/*
input
10 9 0
0 8
8 9
0 4
4 7
4 5
5 6
0 1
1 2
2 3

output
0 1 2 3 4 5 6 7 8 9
*/

1. 시작 노드를 스택에 넣고 방문 표시를 한다.

2. 스택 top에서 노드를 꺼낸다.

3. 꺼낸 노드의 인접 노드 중 아직 방문하지 않은 노드를 스택에 넣고 방문 표시를 한다.

4. 스택이 빌 때까지 2~3을 반복한다.

 

- 재귀 호출을 이용한 DFS

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, M, S;
vector<int> graph[100];
vector<int> visited;
vector<int> result;

void input()
{
    cin >> N >> M >> S;
    visited.resize(N);
    fill(visited.begin(), visited.end(), 0);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs(int S)
{
    if (!visited[S])
    {
        visited[S] = 1;

        result.push_back(S);

        for (int next : graph[S])
        {
            if (!visited[next])
            {
                dfs(next);
            }
        }
    }
}

void output()
{
    for (int i : result)
        cout << i << " ";
    cout << endl;
}

int main(void)
{
    input();
    dfs(S);
    output();

    return 0;
}

/*
input
10 9 0
0 1
1 2
2 3
0 4
4 5
5 6
4 7
0 8
8 9

output
0 1 2 3 4 5 6 7 8 9
*/

인자로 받은 노드가 방문되지 않은 노드라면 방문 표시를 하고 인접한 방문 하지 않은 노드를 인자로 하여 DFS를 재귀호출 한다.

 

시간복잡도 : O(V + E)

BFS (Breadth-First-Search, 너비 우선 탐색)

루트 노드 또는 임의 노드에서 인접한 노드 먼저 탐색하는 방법이다. 큐를 통해 구현한다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, M, S;
vector<int> graph[100];
vector<int> visited;
vector<int> result;

void input()
{
    cin >> N >> M >> S;
    visited.resize(N);
    fill(visited.begin(), visited.end(), 0);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void bfs()
{
    queue<int> q;
    q.push(S);
    visited[S] = 1;

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        result.push_back(cur);

        for (int next : graph[cur])
        {
            if (!visited[next])
            {
                q.push(next);
                visited[next] = 1;
            }
        }
    }
}

void output()
{
    for (int i : result)
        cout << i << " ";
    cout << endl;
}

int main(void)
{
    input();
    bfs();
    output();

    return 0;
}

/*
input
10 9 0
0 1
0 2
0 3
1 4
2 5
2 6
3 7
4 8
5 9

output
0 1 2 3 4 5 6 7 8 9
*/

1. 시작 노드를 큐에 넣고 방문 표시를 한다.

2. 큐 front에서 노드를 꺼낸다.

3. 꺼낸 노드의 인접 노드 중 아직 방문하지 않은 노드를 큐에 넣고 방문 표시를 한다.

4. 큐가 빌 때까지 2~3을 반복한다.

 

시간복잡도 : O(V + E)

 

격자 맵에서의 DFS와 BFS

격자 맵에서는 dy, dx로 상하좌우 인접한 노드를 스택 또는 큐에 넣어 탐색한다. 해당 노드가 유효한 범위에 있는지, 방문 하지 않았는지 유무는 isValid 함수를 통해 판별한다. 

 

- DFS

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

struct Point
{
    int y;
    int x;
};

int N, M;
int Map[100][100];
int visited[100][100];
vector<Point> result;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

void input()
{
    cin >> N >> M;

    fill(&visited[0][0], &visited[N - 1][M], 0);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Map[i][j];
        }
    }
}

bool isValid(int y, int x)
{
    return (0 <= y && y < N && 0 <= x && x < M && Map[y][x] == 1 && !visited[y][x]);
}

void dfs(Point S)
{
    if (isValid(S.y, S.x))
    {
        visited[S.y][S.x] = 1;

        result.push_back(S);

        for (int i = 0; i < 4; i++)
        {
            int ny = S.y + dy[i];
            int nx = S.x + dx[i];
            if (isValid(ny, nx))
            {
                dfs({ny, nx});
            }
        }
    }
}

void output()
{
    for (Point i : result)
        cout << "{" << i.y << ", " << i.x << "} ";
    cout << endl;
}

int main(void)
{
    input();
    dfs({0, 0});
    output();

    return 0;
}

 

- BFS

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

struct Point
{
    int y;
    int x;
};

int N, M, S;
int Map[100][100];
int visited[100][100];
vector<Point> result;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

void input()
{
    cin >> N >> M;

    fill(&visited[0][0], &visited[N - 1][M], 0);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Map[i][j];
        }
    }
}

bool isValid(int y, int x)
{
    return (0 <= y && y < N && 0 <= x && x < M && Map[y][x] == 1 && !visited[y][x]);
}

void bfs()
{
    Point S = {0, 0};
    queue<Point> q;
    q.push(S);
    visited[S.y][S.x] = 1;

    while (!q.empty())
    {
        Point cur = q.front();
        q.pop();

        result.push_back(cur);

        for (int i = 0; i < 4; i++)
        {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (isValid(ny, nx))
            {
                q.push({ny, nx});
                visited[ny][nx] = 1;
            }
        }
    }
}

void output()
{
    for (Point i : result)
        cout << "{" << i.y << ", " << i.x << "} ";
    cout << endl;
}

int main(void)
{
    input();
    bfs();
    output();

    return 0;
}