[1260] DFS와 BFS (C++)

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

using namespace std;

vector<vector<int>> A;
vector<bool> visited;

void DFS(int v);
void BFS(int v);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, v; cin >> N >> M >> v;
    A.resize(N + 1);
    visited = vector<bool>(N + 1, false);

    for (int i = 0; i < M; i++) {
        int s, e;
        cin >> s >> e;
        A[s].push_back(e);
        A[e].push_back(s);
    }

    for (int i = 0; i < A.size(); i++)
        sort(A[i].begin(), A[i].end());

    DFS(v);
    cout << "\n";
    fill(visited.begin(), visited.end(), false);
    BFS(v);
    cout << "\n";

    return 0;
}

void DFS(int v) {
    cout << v << " ";
    visited[v] = true;    

    for (int i : A[v]) {
        if (!visited[i])
            DFS(i);
    }
}

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 : A[x]) {
            if (!visited[i]) {
                visited[i] = true;
                Q.push(i);                
            }
        }
    }   
}

 

1. 각 정점들은 인접 리스트로 받아온 후 sort를 사용해 정렬

2. DFS는 재귀함수로 구현

3. BFS는 queue를 사용해 구현

 

BFS 내 A[x]를 A[v]로 적는 실수를 한 문제