백준 1260번 - DFS 와 BFS C++

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

1260번: DFS와 BFS

탐색알고리즘의 종류인 DFS와 BFS를 구현하는 문제이다.

깊이우선탐색인 DFS(Depth First Search) 와 너비우선탐색인 BFS(Breadth First Search) 는 정점의 시작부터 끝까지 연결되어 있는 모든 노드들을 탐색하는 방법은 똑같으나 순서의 차이가 있다.

1번 테스트케이스

첫번째 테스트케이스를 보면 위와같이 그래프가 구성되어 있다.

DFS는 깊이 우선탐색이므로 1 -> 2-> 4 로 가장깊은곳으로 탐색을 시작한다.

이때 4가 3과 연결되어 있으므로 3까지간후 더이상갈곳이 없으므로 돌아온다.

그래서 출력순서가 1 2 4 3 순으로 출력된다.

 

BFS의 경우 시작정점 1에서 갈수있는 2 3 4 를 차례대로 방문한다.

그래서 출력이 1 2 3 4 로 출력이 되는것이다.

DFS와 BFS의 구현방법의 차이는 DFS는 스택 자료구조를 사용하고,  BFS는 큐 자료구조를 사용한다.

DFS는 스택을 이용하여 구현하는 방법도 있지만 나는 재귀함수로 구현하였다.

 

BFS 함수를 살펴보면 memset함수를 사용하였는데, 이유는 dfs 함수를 먼저 실행하였기 때문에 노드를 방문한적이 있는지 체크하는 check 배열을 초기화 시켜주기 때문에 사용하였다.

메인에서 정렬하는 이유는 문제에서 번호순으로 정렬시켰기 때문에 나역시 정렬을 하였다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

vector<int> a[1001];
bool check[1001];

void dfs(int node) {
    check[node] = true;
    printf("%d ", node);
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if(check[next] == false) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    memset(check, false,sizeof(check));
    check[start] = true;
    q.push(start);
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        printf("%d ", node);
        for(int i=0; i<a[node].size(); i++) {
            int next = a[node][i];
            if(check[next] == false) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}


int main(void)
{
    int n,m, start;
    scanf("%d %d %d", &n,&m,&start);
    for(int i=0; i<m; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=0; i<=n; i++){
        sort(a[i].begin(), a[i].end());
    }
    dfs(start);
    cout << endl;
    bfs(start);
    return 0;
}