[백준 / c++] 1260. DFS와 BFS

문제 ⭐️

코드 💻

#include <iostream>
#include <queue>
using namespace std;

int n, m, v; // 정점, 간선, 탐색을 시작할 정점의 번호
int arr[1001][1001];
bool visitt[1001];

void reset_visit() {
    for(int i=1; i<=n; i++){
        visitt[i]=false;
    }
}

/// 깊이 우선 탐색
void dfs(int v) {
    visitt[v]= true;
    cout << v << " ";
    
    for(int i=1; i<=n; i++){
        // 이미 방문한 노드이거나, 간선이 없는 경우 탐색하지 않음
        if(visitt[i] == true || arr[v][i] == 0)
            continue;
        dfs(i);
        // continue는 여기로 이동
    }
}

/// 너비 우선 탐색
void bfs(int v){
    queue<int> q;
    q.push(v);
    visitt[v] = true;
    cout << v << " ";
    
    while(!q.empty()) {
        v= q.front();
        q.pop();
        
        for(int i=1; i<=n; i++){
            
            // 방문하지 않았고 간선이 연결되어 있는 노드는 모두 탐색
            if(arr[v][i] == 1 && visitt[i] == false){
                q.push(i);
                visitt[i]=true;
                cout << i << " ";
            }
        }
    }
}

int main() {
    
    cin >> n >> m >> v;
    
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        
        arr[x][y]=1;
        arr[y][x]=1;
    }
    reset_visit();
    dfs(v);
    cout << "\n";
    
    reset_visit();
    bfs(v);
    return 0;
}

풀이

dfs는 v를 바꿔가며 점점 더 깊은 노드로 방문(깊이 우선 탐색)

bfs는 해당 v에 연결돼있는 노드에 하나씩 방문(너비 우선 탐색)