[백준/1260][C++] DFS와BFS

 

BFS와, DFS의 가장 기본적인 문제인듯 싶다.

dfs는 재귀함수로 구현하였고, bfs는 큐를 사용하였다.

먼저 DFS의 경우,

그래프에서 노드간의 연결을 위해 벡터를 사용하였다. 그냥 이차원 배열을 사용해도 좋을 듯 하다.
입력 받으며 벡터에 저장할 때, 해당 그래프가 양방향임을 주의하자
"단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 이라는 문구로 인해 sort가 필수적이다.

그러나 2차원 배열을 통해 1번 노드부터 m번 노드까지 방문하면서 1. 방문한 적이 있는지, 2. x번쨰와 i번째가 연결되어 있는지 확인하는 방식을 사용해도 좋을 듯하다.

다음으로 BFS의 경우, 
우선 시작 노드에 방문 표시를 한 뒤, 큐에 푸시한다.
그리고 큐가 빌때 까지 무한 루프 내부에서 인접 노드를 돌며  방문하지 않은 노드가 있다면 방문 표시를 남기고, 큐에 푸쉬한다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 

bool vis_dfs[1002];
bool vis_bfs[1002];
vector<int> graph[1002];
int n, m, v;
void dfs(int x){
    vis_dfs[x] = true;
    cout<< x << ' ';
    for(int i=0; i<graph[x].size();i++){
        int y=graph[x][i];
        if(!vis_dfs[y]) dfs(y);
    }
}
void bfs(int x){
    queue<int> q;
    vis_bfs[x] = true; //일단 시작점 방문
    q.push(x);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout<<cur<<' ';
        for(int i=0;i<graph[cur].size();i++){
            int ncur=graph[cur][i];//x에 연결된 인접 노드
            if(vis_bfs[ncur]==false){ //방문 안한 노드라면
                q.push(ncur);//큐에 푸시
                vis_bfs[ncur]=true;//방문 표시
            }
        }
    }
}
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>v;
    for(int i=0;i<m;i++){ //노드간 연결과정
        int x,y;
        cin>>x>>y;
        graph[x].push_back(y);//양방향
        graph[y].push_back(x);
    }
    for(int i=1;i<=n;i++) 
        sort(graph[i].begin(), graph[i].end());
    // 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

    dfs(v);
    cout<<"\n";
    bfs(v);
}