[DFS/BFS]백준1260번 DFS와 BFS

백준1260

백준 1260번

DFS와 BFS

DFS는 깊이 우선 탐색으로, 하나의 노드를 방문할 때마다 인접한 노드와 인접한 노드로부터 갈 수 있는 모든 노드를 방문하는 방법이다.

매 단계에서 가능한 것 중 일단 하나를 선택해 끝을 볼 때까지 들어간다.

보통 재귀 또는 스택으로 구현한다.

void dfs(int n){
    cout << n << " ";
    visited_dfs[n] = true;
    for(int i=0;i<arr_dfs[n].size();i++){
        if(!visited_dfs[arr_dfs[n][i]]){
            visited_dfs[arr_dfs[n][i]] = true;
            dfs(arr_dfs[n][i]);
        }
    }
}

방문 여부를 확인하고, 매개변수로 들어온 노드에 인접한 노드들을 방문한다.

다만, 각각의 인접한 노드로부터 갈 수 있는 노드를 모두 방문하고 그 다음 인접한 노드로 방문한다.

BFS는 너비 우선 탐색으로, 하나의 노드를 방문할 때마다 해당 노드에 인접한 노드들을 모두 방문한다.

해당 노드에 인접한 노드들을 방문하면서 각 노도들에 인접한 노드들을 다음에 방문할 노드로 추가한다.

void bfs(){
    queue<int> q;
    q.push(V);
    visited_bfs[V] = true;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << " " ;
        for(int i=0;i<arr_bfs[cur].size();i++){
            if(!visited_bfs[arr_bfs[cur][i]]){
                q.push(arr_bfs[cur][i]);
                visited_bfs[arr_bfs[cur][i]] = true;
            }
        }
    }
}

출처 : https://vivadifferences.com/difference-between-dfs-and-bfs-in-artificial-intelligence/

DFS의 특징

1. DFS는 루트 노드로부터 순회를 시작하고, 루트노드로부터 가능한 멀리 탐색한다.
2. DFS 알고리즘은 두 가지 단계로 나뉘어 동작한다.
   1. 노드들을 방문하며 stack 에 push 한다.
   2. 더 이상 방문할 노드가 없다면, stack에서 pop g ksek.
3. DFS 탐색은 stack을 이용해 구현될 수 있다.
4. DFS는 최단 거리 탐색에는 도움이 되지 않는다.
5. DFS는 BFS에 비해 빠르다.
6. DFS 의 시간 복잡도는 O(V+E) 인데, V 는 노드의 개수, E는 edge의 개수이다.
7. DFS는 BFS 에 비해 메모리를 덜 필요로 한다.

BFS의 특징

1. BFS는 루트 노드로부터 순회를 시작하고, 각 레벨(루트 노드에 가까운 정도) 별로 탐색을 수행한다.
2. BFS 알고리즘은 하나의 단계로 이루어진다.
   1. 방문된 노드는 queue에서 제거된다.
   2. 방문할 노드는 queue에 추가된다.
3. BFS는 queue의 도움을 받아 구현될 수 있다.
4. BFS는 최단 거리를 찾는데 유용하다. BFS는 시작 노드로부터 나머지 그래프들까지 중 최단 거리를 찾을 수 있다.
5. BFS 는 DFS 에 비해 느리다.
6. BFS의 시간 복잡도는 O(V+E) 이다. V는 노드의 개수, E는 edge 수를 가리킨다.
7. BFS는 DFS이 비해 많은 메모리를 요구한다.

위에서 구현한대로 함수를 만들고 main 함수는 함수를 호출해서 사용한다.

다만 문제에서 정점 번호가 작은 것부터 방문한다고 하였기 때문에, 함수 수행 전에 배열을 한 번 정렬해주었다.

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

using namespace std;

int N,M,V;
vector<int> arr_bfs[1001];
bool visited_bfs[1001] ={false,};
vector<int> arr_dfs[1001];
bool visited_dfs[1001]={false,};

void bfs(){
    queue<int> q;
    q.push(V);
    visited_bfs[V] = true;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << " " ;
        for(int i=0;i<arr_bfs[cur].size();i++){
            if(!visited_bfs[arr_bfs[cur][i]]){
                q.push(arr_bfs[cur][i]);
                visited_bfs[arr_bfs[cur][i]] = true;
            }
        }
    }
}

void dfs(int n){
    cout << n << " ";
    visited_dfs[n] = true;
    for(int i=0;i<arr_dfs[n].size();i++){
        if(!visited_dfs[arr_dfs[n][i]]){
            visited_dfs[arr_dfs[n][i]] = true;
            dfs(arr_dfs[n][i]);
        }
    }
}

int main(){
    cin >> N >> M >> V;

    for(int i=0;i<M;i++){
        int node1, node2;
        cin >> node1 >> node2;

        arr_bfs[node1].push_back(node2);
        arr_bfs[node2].push_back(node1);

        arr_dfs[node1].push_back(node2);
        arr_dfs[node2].push_back(node1);
    }

    for(int i=0;i<N;i++){
            sort(arr_bfs[i].begin(),arr_bfs[i].end());
            sort(arr_dfs[i].begin(),arr_dfs[i].end());
    }

    dfs(V);
    cout << endl;
    bfs();
   
    
}