[백준] 1260_DFS와BFS_C++

📌 문제

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

---

📥 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

---

📤 출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

💻 접근방법

DFS는 재귀를 통해 구현한다.
매개 변수로 graph,visited,start_vertex가 필요하다.
처음 정점부터 visited 방문 했다고 체크하고, start_vertex 기준으로 간선으로 연결되어 있는 정점들을 방문해 나간다.

BFS는 큐(Queue)가 필요하다.
매개변수로는 DFS와 같이 graph,visited,start_vertex가 필요하다.
시작 정점을 큐에 넣어주고, while문을 돌린다.
큐가 비어 있지 않으면 돌아가는 조건으로 설정하고, visited 에 값이 false로 나오는 정점들을 차례차례 큐에 넣어준다.

---

🍎 정답코드

// DFS, BFS 결과

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

void DFS(vector<vector<int>>&graph,vector<bool>&visited,int start_vertex){
    visited[start_vertex]=true;
    cout<<start_vertex<<" ";
    for(int i=0;i<graph[start_vertex].size();i++){
        if(visited[graph[start_vertex][i]]==false){
            DFS(graph,visited,graph[start_vertex][i]);
        }
    }
}

queue<int>que;

void BFS(vector<vector<int>>&graph, vector<bool>&visited,int start_vertex){
    visited[start_vertex]=true;
    cout<<start_vertex<<" ";
    que.push(start_vertex);
    while(!que.empty()){
        int vertex=que.front();
        que.pop();
        for(auto near_vertex:graph[vertex]){
            if(visited[near_vertex]==false){
                visited[near_vertex]=true;
                que.push(near_vertex);
                cout<<near_vertex<<" ";
            }
        }
    }
}


int main(){
    int N,M,V;
    cin>>N>>M>>V;
    vector<vector<int>>graph(N+1);
    vector<bool>visited(N+1,false);
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=0;i<=N;i++){ // N까지 포함해서 정렬
        sort(graph[i].begin(),graph[i].end());
    }
    DFS(graph,visited,V);
    cout<<"\n";
    for(int i=0;i<visited.size();i++){
        visited[i]=false;
    }
    BFS(graph,visited,V);

}