[Algorithm][백준:1260] DFS와 BFS - C++

시작하며

백준 알고리즘 사이트의 예제를 통해 DFS와 BFS를 정리 기록하고자 한다. 개념적인 부분은 이미 정리를 했기때문에 코드를 통한 구현 방식을 기억하자

링크 : https://www.acmicpc.net/problem/1260

문제

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력

1 2 4 3
1 2 3 4

DFS - 깊이 우선 탐색

깊이 우선 탐색에 대한 방식은 스택이나 재귀함수로 구현

스택으로 구현

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

using namespace std;

vector<int> adjList[1001];
bool visited[1001] = { false };

void dfs_stack(int start) 
{
    // 시작 정점 삽입 
    stack<int> st;
    st.push(start);
    while (!st.empty())
    {
        int current = st.top();
        st.pop();
        if (visited[current])
            continue;

        visited[current] = true;
        printf("%d ", current);

        for (int i = adjList[current].size()-1; i >= 0; i--)
        { 
            int next = adjList[current][i];
            st.push(next);
        }
    }
}

int main() 
{
    int n, m, start;
    cin >> n >> m >> start;

    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;

        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) 
    {
        sort(adjList[i].begin(), adjList[i].end());
    }

    dfs_stack(start);
    printf("\n");

    return 0;
}

재귀 함수로 구현

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

using namespace std;

vector<int> adjList[1001];
bool visited[1001] = { false };

void dfs_recursive(int start)
{
    visited[start] = true;
    printf("%d ", start);

    for (int i = 0; i < adjList[start].size(); i++) {
        int next = adjList[start][i];
        if (visited[next] == false) {
            dfs_recursive(next);
        }
    }
}

int main() 
{
    int n, m, start;
    cin >> n >> m >> start;

    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;

        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) 
    {
        sort(adjList[i].begin(), adjList[i].end());
    }

    dfs_stack(start);
    printf("\n");

    return 0;
}

BFS - 너비 우선 탐색

너비 우선 탐색은 큐를 이용하여 구현

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

using namespace std;

vector<int> adjList[1001];
bool visited[1001] = { false };

void bfs(int start) 
{
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) 
    {
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for (int i = 0; i < adjList[current].size(); i++)
        {
            if (visited[adjList[current][i]] == false) {
                q.push(adjList[current][i]);
                visited[adjList[current][i]] = true;
            }
        }
    }
}

int main() 
{
    int n, m, start;
    cin >> n >> m >> start;

    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;

        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) 
    {
        sort(adjList[i].begin(), adjList[i].end());
    }

    dfs_stack(start);
    printf("\n");

    return 0;
}

요약

DFS는 스택과 재귀함수로 구현할 수 있고, BFS는 큐로 구현할수 있음을 기억하자