dfs bfs

이번에 알고리즘 스터디에서 dfs bfs 문제를 풀면서
기본적인 예제를 먼저 풀어봐야 할 것 같아 따로 기본문제를 풀어보았다.

Q. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

1. dfs
   스택이나 재귀함수 사용

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
//DFS: stack이나 재귀함수로 구현
using namespace std;

//dfs에 들어오면 방문한걸로 판단=> 해당 위치에 check true
void dfs(int start, vector<int> graph[], bool check[]){
    check[start]=true; //방문
    printf("%d", start);

    for (int i=0;i<graph[start].size();i++){
        //벡터 탐색
        int next=graph[start][i];
        if(check[next]==false){
            //출발점을 바꿔서 재귀
            dfs(next, graph, check);
        }
    }
}
int main(){
    int n, m, start;
    cin >> n >>m >> start; //노드 개수, 간선 개수, 시작 노드 번호

    vector<int> graph[n+1];//그래프 생성 (벡터로 이루어진 배열)
    bool check[n+1]; //방문 여부 체크할 배열
    fill(check, check+n+1, false);

    for (int i=0;i<m;i++){
        int u,v;
        cin >> u>> v; //간선마다 연결된 두 노드의 번호
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i=1;i<=n;i++){
        sort(graph[i].begin(), graph[i].end()); //벡터 정렬
    }
    dfs(start, graph, check);

    return 0;

}

2. bfs
   Queue 사용

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

//bfs: 큐를 이용해 구현(FIFO)

using namespace std;

void bfs(int start, vector<int> graph[], bool check[]){
    queue<int> q;

    q.push(start);
    check[start]=true;
    
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        printf("%d", tmp);
        for (int i=0;i<graph[tmp].size();i++){
            if (check[graph[tmp][i]]==false){
                q.push(graph[tmp][i]);
                check[graph[tmp][i]]=true;
            }
        }//for문을 통해 tmp와 인접한 노드들 다 방문
    }
}

int main(){
    int n, m , start;
    cin >> n >> m >> start;

    vector<int> graph[n+1];
    bool check[n+1];
    fill(check, check+n+1, false);

    for (int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i=1;i<=n;i++){
        sort(graph[i].begin(), graph[i].end());
    }
    bfs(start, graph, check);
}