1. 문제

BFS, DFS 구현
문제

2. 구현

// link: https://www.acmicpc.net/problem/1260

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

std::vector<int> DFS_answer;

void DFS(const std::vector<std::vector<bool>>& graph, std::vector<int>& visit, const int N, const int current){
    //std::cout << "current: " << current << ", count: " << count << std::endl;
    visit[current] = 1;
    DFS_answer.push_back(current);

    for (int i=1; i<=N; ++i){
        if ((current == i) || (visit[i] == 1)){
            continue;
        }
        else if(graph[current][i]){
            DFS(graph, visit, N, i);
        }
    }
}

std::vector<int> BFS(const std::vector<std::vector<bool>>& graph, const int N, const int V){
    std::vector<int> answer;
    std::vector<int> visit(N+1, 0);
    std::queue<int> queue;
    queue.push(V);
    answer.push_back(V);
    visit[V] = 1;

    while(!queue.empty()){
        int current = queue.front();
        queue.pop();

        for (int i=1; i<=N; ++i){
            if ((visit[i] == 1) || (current == i)){
                continue;
            }
            else if (graph[current][i]){
                queue.push(i);
                answer.push_back(i);
                visit[i] = 1;
            }
        }
    }

    return answer;
}

int main(){
    int N = 0;
    int M = 0;
    int V = 0;

    std::cin >> N;
    std::cin >> M;
    std::cin >> V;

    std::vector<std::vector<bool>> graph(N+1, std::vector<bool>(N+1, false));

    for (int i=0; i<M; ++i){
        int from = 0;
        int to = 0;
        std::cin >> from >> to;

        graph[from][to] = true;
        graph[to][from] = true;
    }

    std::vector<int> visit_DFS(N+1, 0);

    DFS(graph, visit_DFS, N, V);
    for (int i=0; i<DFS_answer.size()-1; ++i){
        std::cout << DFS_answer[i] << " ";
    }
    std::cout << DFS_answer[DFS_answer.size()-1] << std::endl;

    std::vector<int> BFS_answer = BFS(graph, N, V);
    for (int i=0; i<BFS_answer.size()-1; ++i){
        std::cout << BFS_answer[i] << " ";
    }
    std::cout << BFS_answer[BFS_answer.size()-1] << std::endl;

    return 0;
}