[BOJ_C++] 1260번 : DFS와 BFS

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int n, m, v;
int map[1001][1001];
bool flag[1001];
queue<int> q;

void dfs(int v) {
    flag[v] = true;
    cout << v << " ";        
    
    for (int i = 1; i <= n; i++) {
        if (map[v][i] == 1 && flag[i] == false)
            dfs(i);
    }
}

void bfs(int v) {
    q.push(v);
    flag[v] = true;
    cout << v << " ";

    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (map[v][i] == 1 && flag[i] == false) {
                q.push(i);
                flag[i] = true;
                cout << i << " ";
            }
        }
    }

}

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

    int x, y;
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        map[x][y] = map[y][x] = 1;
    }

    memset(flag, false, sizeof(flag));
    dfs(v);

    cout << "\n";

    memset(flag, false, sizeof(flag));
    bfs(v);

    return 0;
}

 

• dfs는 깊이 우선 탐색으로 해당 노드에서 인접한 노드가 있다면 그 노드를 탐색하고 그렇지 않으면 옆 노드로 이동하여 탐색하게 된다.
• bfs는 너비 우선 탐색으로 해당 노드의 부모와 연결된 모든 노드를 탐색하고 더 이상 탐색할 노드가 없으면 해당 노드와 연결된 노드로 이동하며 탐색하게 된다.

결과