[BOJ / C++] #1260 DFS와 BFS

문제 풀이

기본적인 DFS, BFS 탐색 문제이다.
DFS는 재귀호출, BFS는 큐를 이용해 구현했다.
이때 그래프는 벡터 배열을 이용한 인접리스트로 나타내었고,
두 정점사이에 여러 간선이 있을 수 있으므로 각 배열마다 오름차순으로 정렬해주었다.
방문했는지 검사하는 visited배열 변수도 잊지 말기!

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1001

int N, M, V;
vector<int> map[MAX];
bool visited[MAX];

void dfs(int v){
    cout<<v<<" ";

    for(int i : map[v]){
        if(!visited[i]){
            visited[i]=true;
            dfs(i);
        }
    }

}

void bfs(int v){
    queue<int> q;

    q.push(v);
    visited[v]=true;

    while(!q.empty()){
        int idx=q.front();
        q.pop();
        cout<<idx<<" ";

        for(int i : map[idx]){
            if(!visited[i]){
                q.push(i);
                visited[i]=true;
            }
        }
    }

}

int main(){
    cin>>N>>M>>V;
    for(int i=0;i<M;i++){
        int a, b;
        cin>>a>>b; //양방향
        map[a].push_back(b);
        map[b].push_back(a);
    }

    for(int i=1;i<=N;i++){
        sort(map[i].begin(),map[i].end());
    }

    visited[V]=true;
    dfs(V);
    cout<<"\n";

    //visited 초기화
    memset(visited, false, sizeof(visited));
    bfs(V);
    cout<<"\n";

    return 0;


}